Locally testable code: Difference between revisions

Revision as of 20:20, 24 November 2021

Revision as of 20:34, 24 November 2021

Line 15:

:* For any <math>x\in\{0,1\}^k</math> and <math>w=C(x)</math>, <math>Pr[M^w(1^k)=1]=1</math>. In other words, M accepts given access to any codeword of C.

:* For <math>w\in\{0,1\}^n</math> such that <math>\delta(w,C)>\delta</math>, <math>Pr[M^w(1^k)=1]\leq1/2</math>. M must reject strings <math>\delta</math>-far from C at least half the time.

Also the rate of a code is the ratio between its message length and codeword length

:<math>\frac{|x|}{|C(x)|}</math>

== Limits ==

It remains an open question whether there are any locally testable codes of linear size, but there are several constructions that are considered "nearly linear":<ref name=shortLTC>{{cite web|url=http://eccc.hpi-web.de/eccc-reports/2005/TR05-014/index.html|title=Short Locally Testable Codes and Proofs (Survey)|first=Oded|last=Goldreich|citeseerx = 10.1.1.110.2530}}</ref>

Line 28 ⟶ 29:

The next nearly linear goal is linear up to a [[polylogarithmic]] factor; <math>n=\text{poly}(\log k)*k</math>. Nobody has yet to come up with a linearly testable code that satisfies this constraint.<ref name=shortLTC/>

In 2021 a preprint has reported<ref>{{Cite journal|last=Dinur|first=Irit|last2=Evra|first2=Shai|last3=Livne|first3=Ron|last4=Lubotzky|first4=Alexander|last5=Mozes|first5=Shahar|date=2021-11-08|title=Locally Testable Codes with constant rate, distance, and locality|url=http://arxiv.org/abs/2111.04808|journal=arXiv:2111.04808 [cs, math]}}</ref><ref>{{Cite web|last=Rorvig|first=Mordechai|date=2021-11-24|title=Researchers Defeat Randomness to Create Ideal Code|url=https://www.quantamagazine.org/researchers-defeat-randomness-to-create-ideal-code-20211124/|url-status=live|access-date=2021-11-24|website=[[Quanta Magazine]]|language=en}}</ref> the first polynomial-time construction of "<math>c^3</math>-LTCs" namely locally testable codes with constant rate <math>r</math>, constant distance <math>\delta</math> and constant locality <math>q</math>.

== Connection with probabilistically checkable proofs ==

Line 57:

Other locally testable codes include [[Reed-Muller codes]] (see [[locally decodable code]]s for a decoding algorithm), [[Reed-Solomon code]]s, and the short code.

==See also==

*[[Gilbert–Varshamov bound]]

== References ==