טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentViderman Michael
SubjectTowards Lower Bounds on Locally Testable Codes
DepartmentDepartment of Computer Science
Supervisor Professor Eliyahu Ben Sasson
Full Thesis textFull thesis text - English Version


Abstract

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).