Imperfect gaps in Gap-ETH and PCPs

DOI10.4230/LIPICS.CCC.2019.32MaRDI QIDQ5091784zbMATH OpenOpenAlexFDO

Authors Mitali Bafna, Nikhil Vyas

Publication date 27 July 2022

Full work available at URL https://arxiv.org/abs/1907.08185

zbMATH Keywords

gap-ETHhardness of approximationPCP

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The PCP theorem by gap amplification
• Query efficient PCPs with perfect completeness
• The PCP theorem by gap amplification
• Three‐query PCPs with perfect completeness over non‐Boolean domains
• Smooth and strong PCPs

Cites work

• A birthday repetition theorem and complexity of approximating dense CSPs
• A Chernoff Bound for Random Walks on Expander Graphs
• A Parallel Repetition Theorem
• A sample of samplers: a computational perspective on sampling
• Approximation resistance from pairwise independent subgroups
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• ETH-hardness of approximating 2-CSPs and directed Steiner network
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Hardness amplification for entangled games via anchoring
• On the complexity of k-SAT
• On the power of unique 2-prover 1-round games
• Parallel repetition in projection games and a concentration bound
• Parameterized intractability of even set and shortest vector problem from Gap-ETH
• Proof verification and the hardness of approximation problems
• Short PCPs with Polylog Query Complexity
• Some optimal inapproximability results
• The PCP theorem by gap amplification
• Towards a proof of the 2-to-1 games conjecture?

Cited in

(2)

• scientific article; zbMATH DE number 7087310 (Why is no real title available?)
• Hamming weight proofs of proximity with one-sided error

This page was built for publication: Imperfect gaps in Gap-ETH and PCPs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5091784)