Haifa University - Dept. of CS Theory Seminar Speaker : Or Meir, Weizmann. Title: "Combinatorial Construction of Locally Testable Codes" Date: Thursday, Dec. 20. Place: Haifa U. Education Building, room 570. Time: 12:15 - 13:30 Abstract: An error correcting code is said to be \sf{locally testable} if there is a test that can check whether a given string is a codeword of the code, or rather far from the code, by reading only a constant number of symbols of the string. Locally Testable Codes (LTCs) were first explicitly studied by Goldreich and Sudan (J. ACM 53(4)) and since then few constructions of LTCs were suggested. LTCs are connected with Probabilistically Checkable Proofs (PCPs) and can be seen as the "combinatorial counterparts" of PCPs. Since they are simpler objects then PCPs, one might expect that constructing LTCs would be easier than constructing PCPs. However, all the known constructions either use PCP as a building block, or imply directly the existence of a PCP. In this work we present a new and simpler construction of LTCs that seems to be strictly weaker than PCP. Another important feature of our construction is that it is purely combinatorial, while previous constructions were very algebraic. Finally, our construction matches the parameters of the best known construction of LTCs by Ben-Sasson and Sudan (STOC 2005) and Dinur (STOC 2006).