More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP

DOI10.1002/RSA.20226MaRDI QIDQ3608306zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

approximation hardnessprobabilistically checkable proofsquery efficiencyprobabilistic proof systems

Mathematics Subject Classification ID

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)

Recommendations

• STACS 2005
• A PCP characterization of NP with optimal amortized query complexity
• Query efficient PCPs with perfect completeness
• Towards an optimal query efficient PCP?
• Two-query PCP with subconstant error

Cites work

• scientific article; zbMATH DE number 1775415 (Why is no real title available?)
• A PCP characterization of NP with optimal amortized query complexity
• A Parallel Repetition Theorem
• A new multilayered {PCP} and the hardness of hypergraph vertex cover
• A threshold of ln n for approximating set cover
• Approximation resistant predicates from pairwise independence
• Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness
• Gowers uniformity, influence of variables, and PCPs
• Interactive proofs and the hardness of approximating cliques
• On Unapproximable Versions of $NP$-Complete Problems
• On the power of unique 2-prover 1-round games
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• Query efficient PCPs with perfect completeness
• STACS 2005
• Self-testing/correcting with applications to numerical problems
• Simple analysis of graph tests for linearity and PCP
• Some optimal inapproximability results
• 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.

Cited in

(19)

• Polynomially low error PCPs with \(\operatorname{polyloglog} n\) queries via modular composition
• Black-box reductions in mechanism design
• An improved dictatorship test with perfect completeness
• scientific article; zbMATH DE number 1405801 (Why is no real title available?)
• Max NP-completeness made easy
• Near-optimal NP-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)
• Query efficient PCPs with perfect completeness
• Smooth and strong PCPs
• Two-query PCP with subconstant error
• A PCP characterization of NP with optimal amortized query complexity
• The quest for strong inapproximability results with perfect completeness
• Conditional Hardness of Approximating Satisfiable Max 3CSP-q
• STACS 2005
• Short PCPs with projection queries
• A 3-query PCP over integers
• A two-prover one-round game with strong soundness
• Towards an optimal query efficient PCP?
• scientific article; zbMATH DE number 1775415 (Why is no real title available?)
• A query efficient non-adaptive long code test with perfect completeness

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)