An Improved Dictatorship Test with Perfect Completeness
From MaRDI portal
Publication:5136305
DOI10.4230/LIPIcs.FSTTCS.2017.15zbMath1491.68083arXiv1702.04748OpenAlexW2591560904MaRDI QIDQ5136305
Amey Bhangale, Subhash A. Khot, Devanathan Thiruvenkatachari
Publication date: 25 November 2020
Full work available at URL: https://arxiv.org/abs/1702.04748
Analysis of algorithms and problem complexity (68Q25) Boolean functions (06E30) Randomized algorithms (68W20)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation resistant predicates from pairwise independence
- Gaussian bounds for noise correlation of functions
- Proof verification and the hardness of approximation problems
- A PCP characterization of NP with optimal amortized query complexity
- A query efficient non-adaptive long code test with perfect completeness
- On the power of unique 2-prover 1-round games
- More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP
- Probabilistic checking of proofs
- A Parallel Repetition Theorem
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Testing Basic Boolean Formulae
- Simple analysis of graph tests for linearity and PCP
- SDP Integrality Gaps with Local ell_1-Embeddability
- Conditional hardness for satisfiable 3-CSPs
- Gowers Uniformity, Influence of Variables, and PCPs
- A characterization of strong approximation resistance
- Hypercontractivity of simple random variables
- On the NP-Hardness of Max-Not-2
- Some optimal inapproximability results
- Approximation resistance from pairwise independent subgroups
- Approximation resistance on satisfiable instances for predicates with few accepting inputs
This page was built for publication: An Improved Dictatorship Test with Perfect Completeness
