New direct-product testers and 2-query PCPs
From MaRDI portal
Publication:5172706
DOI10.1145/1536414.1536435zbMath1304.68048MaRDI 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
68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W20: Randomized algorithms
68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
Related Items
Composition of Low-Error 2-Query PCPs Using Decodable PCPs, Some Recent Results on Local Testing of Sparse Linear Codes, Direct Sum Testing, Derandomized parallel repetition via structured PCPs, Towards lower bounds on locally testable codes via density arguments