Simple analysis of graph tests for linearity and PCP

DOI10.1002/RSA.10068MaRDI QIDQ4800393zbMATH OpenOpenAlexWikidataFDO

Authors A. Wigderson, Johan Hastad

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

zbMATH Keywords

pseudorandomnesslinearity testingPCPgraph testiterated test

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 1775415
• Locally testable codes and PCPs of almost-linear length
• Lower bounds for adaptive linearity tests
• A PCP characterization of NP with optimal amortized query complexity
• scientific article; zbMATH DE number 1559564

Cites work

• scientific article; zbMATH DE number 3609704 (Why is no real title available?)
• A Parallel Repetition Theorem
• A threshold of ln n for approximating set cover
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Hardness vs randomness
• Interactive proofs and the hardness of approximating cliques
• Linear-consistency testing.
• Linearity testing in characteristic two
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• Self-testing/correcting with applications to numerical problems
• Some optimal inapproximability results

Cited in

(21)

• Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs
• Sparse hypergraphs with applications to coding theory
• Breaking the ε-Soundness Bound of the Linearity Test over GF(2)
• Lower bounds for adaptive linearity tests
• More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP
• Black-box reductions in mechanism design
• Query-efficient dictatorship testing with perfect completeness
• Finding large 3-free sets. I. The small \(n\) case
• scientific article; zbMATH DE number 1775415 (Why is no real title available?)
• A self-tester for linear functions over the integers with an elementary proof of correctness
• On the derandomization of the graph test for homomorphism over groups
• On the communication complexity of high-dimensional permutations
• On non-optimally expanding sets in Grassmann graphs
• Characterizations of locally testable linear- and affine-invariant families
• scientific article; zbMATH DE number 7053293 (Why is no real title available?)
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• On regularity lemma and barriers in streaming and dynamic matching
• An improved dictatorship test with perfect completeness
• A query efficient non-adaptive long code test with perfect completeness
• Colorings with only rainbow arithmetic progressions
• Improved low-degree testing and its applications

This page was built for publication: Simple analysis of graph tests for linearity and PCP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4800393)