More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP
From MaRDI portal
Publication:3608306
DOI10.1002/rsa.20226zbMath1159.68033OpenAlexW4244547255MaRDI 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
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (5)
A query efficient non-adaptive long code test with perfect completeness ⋮ Unnamed Item ⋮ Black-Box Reductions in Mechanism Design ⋮ The Quest for Strong Inapproximability Results with Perfect Completeness ⋮ An Improved Dictatorship 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
This page was built for publication: More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP
