Ph.D Student | Viderman Michael |
---|---|

Subject | Towards Lower Bounds on Locally Testable Codes |

Department | Department of Computer Science |

Supervisor | Professor Eliyahu Ben Sasson |

Full Thesis text |

Locally testable codes (LTCs) are error-correcting codes for which membership, in the code, of a given word can be tested by examining it in very few locations. The main open problem in the area of locally testable codes (LTCs) is whether there exists an asymptotically good family of LTCs, i.e., LTCs with constant rate, constant relative distance and constant query complexity. In this thesis we suggest an approach to refute the existence of asymptotically good linear LTCs.

Without loss of generality we may deal with the case of query complexity 3. Our proof-strategy goes by way of contradiction and relies on proving the following pair of conjectures.

1)
If *C* is an asymptotically good 3-query LTC then *C* has a super-linear
number of dual codewords of weight at most 3.

2)
If *C* is an asymptotically good 3-query LTC and has a super-linear
number of dual codewords of weight at most 3 then rate(*C*)=o(1).

Most known constructions of locally
testable codes are linear codes, and give error-correcting codes whose duals
have *superlinearly* many small weight codewords. Examining this feature
appears to be one of the promising approaches to proving limitation results for
(i.e., upper bounds on the rate of) LTCs. Unfortunately till now it was not
even known if LTCs need to be non-trivially redundant, i.e., need to have *one*
linear dependency among the low-weight codewords in its dual.

In this thesis we give the first
lower bound of this form, by showing that every positive rate constant query
LTC must have linearly many redundant low-weight codewords in its dual. We
actually prove the stronger claim that the *actual test itself* must use a
linear number of redundant dual codewords (beyond the minimum number of basis
elements required to characterize the code); in other words, non-redundant (in
fact, low redundancy) local testing is impossible. Our hope is that this might
be useful to prove the conjecture stated in the first item above. On the other
hand, we progress on the conjecture stated in the second item above, and show
that if *C* has a superlinear number of dual codewords of weight at most 3
which are naturally distributed then rate(*C*)=o(1).