Simple analysis of graph tests for linearity and PCP
From MaRDI portal
Publication:4800393
DOI10.1002/rsa.10068zbMath1064.68070OpenAlexW2087964954WikidataQ56958974 ScholiaQ56958974MaRDI QIDQ4800393
Avi Wigderson, Johan T. Håstad
Publication date: 3 April 2003
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.10068
Related Items
A self-tester for linear functions over the integers with an elementary proof of correctness, A query efficient non-adaptive long code test with perfect completeness, On the derandomization of the graph test for homomorphism over groups, Sparse Hypergraphs with Applications to Coding Theory, Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs, Colorings with only rainbow arithmetic progressions, Finding large 3-free sets. I. The small \(n\) case, Breaking the ε-Soundness Bound of the Linearity Test over GF(2), Query-Efficient Dictatorship Testing with Perfect Completeness, Unnamed Item, More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP, On non-optimally expanding sets in Grassmann graphs, Black-Box Reductions in Mechanism Design, Characterizations of locally testable linear- and affine-invariant families, Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses, Unnamed Item, An Improved Dictatorship Test with Perfect Completeness
Cites Work
- Unnamed Item
- Self-testing/correcting with applications to numerical problems
- Hardness vs randomness
- Linearity testing in characteristic two
- Proof verification and the hardness of approximation problems
- A threshold of ln n for approximating set cover
- Probabilistic checking of proofs
- Interactive proofs and the hardness of approximating cliques
- A Parallel Repetition Theorem
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Some optimal inapproximability results
- Linear-consistency testing.
