More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP
DOI10.1002/RSA.20226zbMATH Open1159.68033OpenAlexW4244547255MaRDI QIDQ3608306FDOQ3608306
Authors: Lars Engebretsen, Jonas Holmerin 
Publication date: 4 March 2009
Published in: Random Structures \& Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.20226
Recommendations
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- A threshold of ln n for approximating set cover
- Proof verification and the hardness of approximation problems
- Probabilistic checking of proofs
- Interactive proofs and the hardness of approximating cliques
- Some optimal inapproximability results
- Self-testing/correcting with applications to numerical problems
- On Unapproximable Versions of $NP$-Complete Problems
- On the power of unique 2-prover 1-round games
- Gowers uniformity, influence of variables, and PCPs
- A PCP characterization of NP with optimal amortized query complexity
- A Parallel Repetition Theorem
- Title not available (Why is that?)
- Simple analysis of graph tests for linearity and PCP
- Approximation resistant predicates from pairwise independence
- A new multilayered {PCP} and the hardness of hypergraph vertex cover
- Query efficient PCPs with perfect completeness
- The Nonapproximability of Non-Boolean Predicates
- Three‐query PCPs with perfect completeness over non‐Boolean domains
- Towards optimal lower bounds for clique and chromatic number.
- Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness
- STACS 2005
Cited In (19)
- Query efficient PCPs with perfect completeness
- A PCP characterization of NP with optimal amortized query complexity
- Polynomially low error PCPs with \(\operatorname{polyloglog} n\) queries via modular composition
- A two-prover one-round game with strong soundness
- Conditional Hardness of Approximating Satisfiable Max 3CSP-q
- A 3-query PCP over integers
- Black-box reductions in mechanism design
- Title not available (Why is that?)
- STACS 2005
- Smooth and strong PCPs
- Two-query PCP with subconstant error
- Title not available (Why is that?)
- Max NP-completeness made easy
- Towards an optimal query efficient PCP?
- The quest for strong inapproximability results with perfect completeness
- An improved dictatorship test with perfect completeness
- A query efficient non-adaptive long code test with perfect completeness
- Near-optimal NP-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)
- Short PCPs with projection queries
This page was built for publication: More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3608306)
