Sub-constant error low degree test of almost-linear size

DOI10.1145/1132516.1132520MaRDI QIDQ2931366zbMATH OpenOpenAlexFDO

Authors Dana Moshkovitz, Ran Raz

Publication date 25 November 2014

Published in Proceedings of the thirty-eighth annual ACM symposium on Theory of 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

locally testable codesprobabilistically checkable proofslow degree testingplane vs. point test

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Specification and verification (program logics, model checking, etc.) (68Q60)

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

(11)

• Approximate testing with error relative to input size.
• Testers and their applications
• Some recent results on local testing of sparse linear codes
• Sub-Constant Error Low Degree Test of Almost-Linear Size
• Characterizations of locally testable linear- and affine-invariant families
• Quantum information and the PCP theorem
• scientific article; zbMATH DE number 1559564 (Why is no real title available?)
• Testing algebraic geometric codes
• Low-degree test with polynomially small error
• scientific article; zbMATH DE number 1500524 (Why is no real title available?)
• Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes

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 Q2931366)