New Direct-Product Testers and 2-Query PCPs

DOI10.1137/09077299XzbMath1275.68069OpenAlexW1999705592MaRDI QIDQ4910583

Avi Wigderson, Valentine Kabanets, Russell Impagliazzo

Publication date: 19 March 2013

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/09077299x

zbMATH Keywords

probabilistically checkable proofsparallel repetition theoremdirect-product tester

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (8)

Cube vs. Cube Low Degree Test. ⋮ Low-degree test with polynomially small error ⋮ Unnamed Item ⋮ ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network ⋮ Fast Reed-Solomon Interactive Oracle Proofs of Proximity ⋮ Unnamed Item ⋮ From Local to Robust Testing via Agreement Testing ⋮ List-Decoding with Double Samplers

This page was built for publication: New Direct-Product Testers and 2-Query PCPs