| A new PCP outer verifier with applications to homogeneous linear equations and max-bisection |
| Full text |
 Pdf
(249 KB)
|
Source
|
Annual ACM Symposium on Theory of Computing
archive
Proceedings of the thirty-sixth annual ACM symposium on Theory of computing
table of contents
Chicago, IL, USA
SESSION: Session 1A
table of contents
Pages: 11 - 20
Year of Publication: 2004
ISBN:1-58113-852-0
|
|
Authors
|
|
Jonas Holmerin
|
Royal Institute of Technology, Stockholm, SWEDEN
|
|
Subhash Khot
|
Georgia Institute of Technology, Atlanta, GA and Institute for Advanced Study, Princeton, NJ
|
|
| Sponsors |
|
| Publisher |
|
| Bibliometrics |
Downloads (6 Weeks): 10, Downloads (12 Months): 73, Citation Count: 1
|
|
|
 ABSTRACT
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 ½+ζ 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(2nε).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.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
S. Arora. The PCP Theorems. Chapter in a book; manuscript.
|
 |
2
|
|
| |
3
|
|
| |
4
|
|
| |
5
|
|
| |
6
|
|
| |
7
|
|
| |
8
|
U. Feige. Personal Communication, 2003.
|
| |
9
|
|
| |
10
|
|
| |
11
|
E. Halperin and U. Zwick. A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems. In Proc. 7th Conference on Integer Programming an Combinatorial Optimization, pages 202--217, 2001.
|
| |
12
|
|
| |
13
|
|
| |
14
|
J. Holmerin and S. Khot. A strong inapproximability result for a generalization of Minimum Bisection. In Proc. 18th IEEE Conference on Computational Complexity, 2003.
|
| |
15
|
|
| |
16
|
|
| |
17
|
S. Khot and O. Regev. Vertex cover might be hard to approximate to within 2-ε. In Proc. 18th IEEE Conference on Computational Complexity, 2003.
|
| |
18
|
|
| |
19
|
|
| |
20
|
|
| |
21
|
Ran Raz , Shmuel Safra, A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.475-484, May 04-06, 1997, El Paso, Texas, United States
[doi> 10.1145/258533.258641]
|
| |
22
|
|
| |
23
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
F.2