Explicit Strong LTCs with inverse poly-log rate and constant soundness

Oded's comments

The question of explicit construction of LTCs of various types was somewhat neglected in light of the focus on the mere existence of LTCs of the desired types. Needless to say, this neglect did not represent lack of interest in explicitness but rather a focus on the primary question of mere existence, which once resolves opens the door to the question of explicitness.

Note (Jan'17): The following overview is based on Or Meir's explanations. The key steps in this sequence of works are:

1. Defining strong PCPPs with respect to two proportion parameters, rather than a single one such that the first (resp., second) parameter lower bounds the the detection probability in terms of the distance of the input-oracle (resp., proof-oracle) from the corresponding property (resp., a valid proof).
2. Showing that Or's and BS's constructions are actually strong PCPPs with respect to a 1/polylog bound for both parameters.
   This was first shown for Or's non-explicit construction, which is the source of the non-explicitness in the previous construction, whereas establishing this for BS's explicit construction yields explicit strong LTCs.
3. Observing that Irit's amplification increases the input-detection parameter but decreases the proof-detection parameters, each by constant factor.
4. Observing that when applying the BGHSV transformation (from PCPPs to LTCs) to a PCPP of constant input-detection parameter and bounded proof-detection parameter yields a strong LTC with length overhead inversely proportional to latter bound.

The original abstract

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.

Strong LTCs with the required range of parameters were obtained recently in the works of Viderman (CCC 2013, FOCS 2013) based on the papers of Meir (SICOMP 2009) and Dinur (J.ACM 2007). However, the construction of these codes was \emph{probabilistic}.

In this work we show that codes presented in the works of Dinur (J.ACM 2007) and Ben-Sasson and Sudan (SICOMP 2005) provide the \emph{explicit} construction of strong LTCs with the above range of parameters. Previously, such codes were proven to be weak LTCs. Using the results of Viderman (CCC 2013, FOCS 2013) we prove that such codes are, in fact, strong LTCs.

See ECCC TR15-020