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

DOI10.1145/780542.780631zbMath1192.94089MaRDI 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

94A60: Cryptography

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

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