Content deleted Content added
Citation bot (talk | contribs) Add: eprint, class, year, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | #UCB_webform_linked 18/33 |
|||
Line 12:
Relative distances are computed as a fraction of the number of bits
:<math>\delta(x,y)=\Delta(x,y)/n \text{ and } \delta(w,C)=\Delta(w,C)/n</math>
A code <math>C:\{0,1\}^k\to\{0,1\}^n</math> is called <math>q</math>-local <math>\delta</math>-testable if there exists a Turing machine M given [[random access]] to an input <math>w</math> that makes at most <math>q</math> non-adaptive queries of <math>w</math> and satisfies the following:<ref name=robustLTC>{{cite web|url=http://people.csail.mit.edu/madhu/papers/2004/rltc-conf.pdf|title=Robust Locally Testable Codes and Products of Codes|first1=Eli|last1=Ben-Sasson|first2=Madhu|last2=Sudan}}</ref>
:* 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.
| |||