New direct-product testers and 2-query PCPs

DOI10.1145/1536414.1536435zbMath1304.68048OpenAlexW2103539404MaRDI QIDQ5172706

Russell Impagliazzo, Avi Wigderson, Valentine Kabanets

Publication date: 4 February 2015

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

Full work available at URL: https://doi.org/10.1145/1536414.1536435

zbMATH Keywords

direct productstestingPCPparallel repetition

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) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (5)

Derandomized parallel repetition via structured PCPs ⋮ Towards lower bounds on locally testable codes via density arguments ⋮ Composition of Low-Error 2-Query PCPs Using Decodable PCPs ⋮ Some Recent Results on Local Testing of Sparse Linear Codes ⋮ Direct Sum Testing

This page was built for publication: New direct-product testers and 2-query PCPs