Imperfect gaps in Gap-ETH and PCPs
From MaRDI portal
Publication:5091784
DOI10.4230/LIPIcs.CCC.2019.32OpenAlexW2966552573MaRDI QIDQ5091784
Publication date: 27 July 2022
Full work available at URL: https://arxiv.org/abs/1907.08185
Related Items (1)
Cites Work
- Unnamed Item
- A Sample of Samplers: A Computational Perspective on Sampling
- Proof verification and the hardness of approximation problems
- Parallel Repetition in Projection Games and a Concentration Bound
- On the power of unique 2-prover 1-round games
- Short PCPs with Polylog Query Complexity
- A Chernoff Bound for Random Walks on Expander Graphs
- A Parallel Repetition Theorem
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Hardness amplification for entangled games via anchoring
- ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network
- Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH
- Towards a proof of the 2-to-1 games conjecture?
- Some optimal inapproximability results
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Approximation resistance from pairwise independent subgroups
- The PCP theorem by gap amplification
- On the complexity of \(k\)-SAT
This page was built for publication: Imperfect gaps in Gap-ETH and PCPs
