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

DOI10.1145/1132516.1132520zbMath1301.68128OpenAlexW2049697554MaRDI QIDQ2931366

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

zbMATH Keywords

probabilistically checkable proofslocally testable codeslow 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)

Related Items (4)

Quantum information and the PCP theorem ⋮ Some Recent Results on Local Testing of Sparse Linear Codes ⋮ Characterizations of locally testable linear- and affine-invariant families ⋮ Testing algebraic geometric codes

This page was built for publication: Sub-constant error low degree test of almost-linear size