אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

An error-correcting code $C \subseteq \F^n$ is called $(q,\epsilon)$-strong locally testable code (LTC) if there exists a tester that makes at most $q$ queries to the input word. This tester accepts all codewords with probability 1 and rejects all non-codewords $x\notin C$ with probability at least $\epsilon \cdot \delta(x,C)$, where $\delta(x,C)$ denotes the relative Hamming distance between the word $x$ and the code $C$. The parameter $q$ is called the query complexity and the parameter $\epsilon$ is called soundness.

Goldreich and Sudan (J.ACM 2006) asked about the existence of strong LTCs with constant query complexity, constant relative distance, constant soundness and inverse polylogarithmic rate. They also asked about the explicit constructions of these codes.

A major progress towards resolving this question was made in the papers of Ben-Sasson and Sudan (SICOMP 2005), Meir (SICOMP 2009) and Dinur (J.ACM 2007). However, the LTCs constructed in these works were weak.

We show explicit strong LTCs with the required range of parameters, therefore resolving this open question. The results described in the talk were obtained in papers of Viderman (CCC 2013, FOCS 2013, ECCC 2015).