Randomness-efficient low degree tests and short PCPs via epsilon-biased sets

DOI10.1145/780542.780631zbMath1192.94089OpenAlexW2146261818MaRDI QIDQ3581280

Madhu Sudan, Avi Wigderson, Eli Ben-Sasson, Salil P. Vadhan

Publication date: 16 August 2010

Published in: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: http://nrs.harvard.edu/urn-3:HUL.InstRepos:2961580

Mathematics Subject Classification ID

Cryptography (94A60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (26)

Quantum Hashing and Fingerprinting for Quantum Cryptography and Computations ⋮ Succinct non-interactive arguments via linear interactive proofs ⋮ A self-tester for linear functions over the integers with an elementary proof of correctness ⋮ Linear-size constant-query IOPs for delegating computation ⋮ Low-degree test with polynomially small error ⋮ Unnamed Item ⋮ On the derandomization of the graph test for homomorphism over groups ⋮ Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes ⋮ Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting) ⋮ Small Sample Spaces Cannot Fool Low Degree Polynomials ⋮ Breaking the ε-Soundness Bound of the Linearity Test over GF(2) ⋮ Testing Odd Direct Sums Using High Dimensional Expanders ⋮ Shorter arithmetization of nondeterministic computations ⋮ Symmetric LDPC codes and local testing ⋮ Short Locally Testable Codes and Proofs: A Survey in Two Parts ⋮ Symmetric LDPC Codes and Local Testing ⋮ Non‐Abelian homomorphism testing, and distributions close to their self‐convolutions ⋮ Short Locally Testable Codes and Proofs ⋮ Testing properties of functions on finite groups ⋮ Characterizations of locally testable linear- and affine-invariant families ⋮ Robust locally testable codes and products of codes ⋮ Unnamed Item ⋮ Testing algebraic geometric codes ⋮ Analysis of properties of quantum hashing ⋮ Computational Integrity with a Public Random String from Quasi-Linear PCPs ⋮ Direct Sum Testing

This page was built for publication: Randomness-efficient low degree tests and short PCPs via epsilon-biased sets