Locally testable code: Difference between revisions

Revision as of 20:51, 24 November 2021

Revision as of 21:40, 24 November 2021

Line 16:

:* 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>r=\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>