More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP
From MaRDI portal
Publication:3608306
DOI10.1002/rsa.20226zbMath1159.68033MaRDI QIDQ3608306
Lars Engebretsen, Jonas Holmerin
Publication date: 4 March 2009
Published in: Random Structures and Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.20226
probabilistically checkable proofs; approximation hardness; query efficiency; probabilistic proof systems
68Q25: Analysis of algorithms and problem complexity
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Unnamed Item, The Quest for Strong Inapproximability Results with Perfect Completeness, An Improved Dictatorship Test with Perfect Completeness, Black-Box Reductions in Mechanism Design, A query efficient non-adaptive long code test with perfect completeness
Cites Work
- Unnamed Item
- Unnamed Item
- Approximation resistant predicates from pairwise independence
- Self-testing/correcting with applications to numerical problems
- Towards optimal lower bounds for clique and chromatic number.
- Gowers uniformity, influence of variables, and PCPs
- Proof verification and the hardness of approximation problems
- A threshold of ln n for approximating set cover
- A PCP characterization of NP with optimal amortized query complexity
- Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness
- On the power of unique 2-prover 1-round games
- A new multilayered PCP and the hardness of hypergraph vertex cover
- Probabilistic checking of proofs
- Interactive proofs and the hardness of approximating cliques
- A Parallel Repetition Theorem
- The Nonapproximability of Non-Boolean Predicates
- Simple analysis of graph tests for linearity and PCP
- Three‐query PCPs with perfect completeness over non‐Boolean domains
- Some optimal inapproximability results
- On Unapproximable Versions of $NP$-Complete Problems
- STACS 2005
