Query-Efficient Dictatorship Testing with Perfect Completeness

DOI10.1007/978-3-642-16367-8_20zbMath1309.68216MaRDI QIDQ4933378

Victor Chen

Publication date: 12 October 2010

Published in: Property Testing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-16367-8_20

zbMATH Keywords

probabilistically checkable proofs; dictatorship test

Mathematics Subject Classification ID

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

68W20: Randomized algorithms

Related Items

Testing Juntas: A Brief Survey

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Proof verification and the hardness of approximation problems
• A PCP characterization of NP with optimal amortized query complexity
• Conditional Hardness for Approximate Coloring
• On the power of unique 2-prover 1-round games
• A Hypergraph Dictatorship Test with Perfect Completeness
• 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
• Conditional hardness for satisfiable 3-CSPs
• Gowers Uniformity, Influence of Variables, and PCPs
• Some optimal inapproximability results
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• STACS 2005
• A new proof of Szemerédi's theorem