Sub-Constant Error Low Degree Test of Almost-Linear Size

DOI10.1137/060656838zbMath1165.68029OpenAlexW2061707159MaRDI QIDQ3614153

Ran Raz, Dana Moshkovitz

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

zbMATH Keywords

samplingprobabilistically checkable proofslow degree testingplane vs. point test

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) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (8)

Cube vs. Cube Low Degree Test. ⋮ Low-degree test with polynomially small error ⋮ Unnamed Item ⋮ Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes ⋮ Derandomized parallel repetition via structured PCPs ⋮ Composition of Low-Error 2-Query PCPs Using Decodable PCPs ⋮ Three-Player Entangled XOR Games are NP-Hard to Approximate ⋮ Unnamed Item

This page was built for publication: Sub-Constant Error Low Degree Test of Almost-Linear Size