Sub-Constant Error Low Degree Test of Almost-Linear Size
From MaRDI portal
Publication:3614153
DOI10.1137/060656838zbMath1165.68029MaRDI QIDQ3614153
Publication date: 16 March 2009
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.429.7381
68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Unnamed Item, Composition of Low-Error 2-Query PCPs Using Decodable PCPs, Unnamed Item, Derandomized parallel repetition via structured PCPs, Low-degree test with polynomially small error, Three-Player Entangled XOR Games are NP-Hard to Approximate