Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A new PCP outer verifier with applications to homogeneous linear equations and Max-Bisection
KTH, Superseded Departments, Numerical Analysis and Computer Science, NADA.
2004 (English)In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery (ACM), 2004, 11-20 p.Conference paper, Published paper (Refereed)
Abstract [en]

We show an optimal hardness result for the following problem : Given a system of homogeneous linear equations over GF(2) with 3 variables per equation, find a balanced assignment that satisfies maximum number of equations. For arbitrarily small constant ζ > 0, we show that it is hard to determine (in polynomial time) whether such a system has a balanced assignment that satisfies 1 - ζ fraction of equations or there is no balanced assignment that satisfies more than 1/2 + ζ fraction of equations, As a corollary, we show that it is hard to approximate (in polynomial time) the Max-Bisection problem within factor 16/15 - ζ These hardness results hold under the assumption NP ⊈ > 0 DTIME(2 nε). Our results are obtained via a construction of a new PCP outer verifier that has a mixing property and a smoothness property. These properties are crucial in the analysis of the inner verifier. No previous outer verifier can achieve both these properties simultaneously. An outer verifier is essentially a 2-query PCP over a large alphabet. Loosely speaking, the mixing property says that the locations of the two queries read by the verifier are uncorrelated. The smoothness property says that the verifier's acceptance predicate is close to being a bijective predicate. Our construction relies on the algebraic techniques used to prove the PCP Theorem. This is in contrast with all earlier constructions that use the PCP Theorem as a black-box. The progress in inapproximability theory seems to require new ideas for building outer verifiers and our construction takes a first step in that direction.

Place, publisher, year, edition, pages
Association for Computing Machinery (ACM), 2004. 11-20 p.
Series
Conference Proceedings of the Annual ACM Symposium on Theory of Computing, ISSN 0734-9025
Keyword [en]
Hardness of Approximation, Linear Equations, Max-Bisection, PCPs
National Category
Other Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-157174Scopus ID: 2-s2.0-4544354754OAI: oai:DiVA.org:kth-157174DiVA: diva2:770698
Conference
The 36th Annual ACM Symposium on Theory of Computing; Chicago, IL; United States; 13 June 2004 through 15 June 2004
Note

QC 20141211

Available from: 2014-12-11 Created: 2014-12-08 Last updated: 2014-12-11Bibliographically approved

Open Access in DiVA

No full text

Scopus

Search in DiVA

By author/editor
Holmerin, Jonas
By organisation
Numerical Analysis and Computer Science, NADA
Other Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 17 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf