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

DOI10.1137/060656838MaRDI QIDQ3614153zbMATH OpenOpenAlexFDO

Authors Dana Moshkovitz, Ran Raz

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

low degree testingplane vs. point testprobabilistically checkable proofssampling

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Sub-constant error low degree test of almost-linear size
• Low-degree test with polynomially small error
• scientific article; zbMATH DE number 1559564
• Cube vs. Cube Low Degree Test.
• Improved low-degree testing and its applications

Cited in

(17)

• Approximate testing with error relative to input size.
• Low-degree test with polynomially small error
• Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes
• Three-player entangled XOR games are NP-hard to approximate
• Sub-constant error low degree test of almost-linear size
• Testers and their applications
• scientific article; zbMATH DE number 1500524 (Why is no real title available?)
• scientific article; zbMATH DE number 1559564 (Why is no real title available?)
• Cube vs. Cube Low Degree Test.
• Composition of low-error 2-query PCPs using decodable PCPs
• On axis-parallel tests for tensor product codes
• On axis-parallel tests for tensor product codes
• Derandomized parallel repetition via structured PCPs
• Rigid matrices from rectangular PCPs
• Boolean function analysis on high-dimensional expanders
• Property testing with online adversaries
• Property testing with online adversaries

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3614153)