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

DOI10.1145/1132516.1132520zbMATH Open1301.68128OpenAlexW2049697554MaRDI QIDQ2931366FDOQ2931366

Ran Raz, Dana Moshkovitz

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

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

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)

Cited In (10)

• Approximate testing with error relative to input size.
• Sub-Constant Error Low Degree Test of Almost-Linear Size
• Characterizations of locally testable linear- and affine-invariant families
• Title not available (Why is that?)
• Quantum information and the PCP theorem
• Testing algebraic geometric codes
• Low-degree test with polynomially small error
• Title not available (Why is that?)
• Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes
• Some Recent Results on Local Testing of Sparse Linear 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)