Content deleted Content added
m →Long code: Link to the right article for "Long code" |
|||
Line 53:
=== Long code ===
The [[Long code (mathematics)|Long code]] is another code with very large blowup which is close to locally testable. Given an input <math>0\leq i\leq2^k</math> (note, this takes <math>k</math> bits to represent), the function that returns the <math>i^{th}</math> bit of the input, <math>f_i(x)=x_i</math>, is evaluated on all possible <math>2^k</math>-bit inputs <math>0\leq x\leq2^{2^k}</math>, and the codeword is the concatenation of these (of length <math>n=2^{2^k}</math>). The way to locally test this with some errors is to pick a uniformly random input <math>x</math> and set <math>y=x</math>, but with a small chance of flipping each bit, <math>\mu>0</math>. Accept a function <math>f</math> as a codeword if <math>f(x)=f(y)</math>. If <math>f</math> is a codeword, this will accept <math>f</math> as long as <math>x_i</math> was unchanged, which happens with probability <math>1-\mu</math>. This violates the requirement that codewords are always accepted, but may be good enough for some needs.<ref name=LongCode>{{cite web|url=http://www.wisdom.weizmann.ac.il/~ranraz/publications/Punique_codes.pdf|title=Bounds on Locally Testable Codes with Unique Tests|first1=Gillat|last1=Kol|first2=Ran|last2=Raz}}</ref>
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.
| |||