Query-efficient dictatorship testing with perfect completeness
From MaRDI portal
Recommendations
- A Hypergraph Dictatorship Test with Perfect Completeness
- An improved dictatorship test with perfect completeness
- A query efficient non-adaptive long code test with perfect completeness
- A query efficient non-adaptive long code test with perfect completeness
- Query efficient PCPs with perfect completeness
Cites work
- A Hypergraph Dictatorship Test with Perfect Completeness
- A new proof of Szemerédi's theorem
- A Parallel Repetition Theorem
- A PCP characterization of NP with optimal amortized query complexity
- Conditional Hardness for Approximate Coloring
- Conditional hardness for satisfiable 3-CSPs
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Gowers Uniformity, Influence of Variables, and PCPs
- scientific article; zbMATH DE number 1775415 (Why is no real title available?)
- Low-degree tests at large distances
- On the power of unique 2-prover 1-round games
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Probabilistic checking of proofs
- Proof verification and the hardness of approximation problems
- Query efficient PCPs with perfect completeness
- Simple analysis of graph tests for linearity and PCP
- Some optimal inapproximability results
- STACS 2005
- Testing Basic Boolean Formulae
Cited in
(4)
This page was built for publication: Query-efficient dictatorship testing with perfect completeness
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4933378)
