Strong LTCs with inverse poly-log rate and constant soundness

by Michael Viderman

Oded's comments

Congrat's to Michael Viderman for resolving this open problem, by building on his prior work.

Unfortunately, the current write-up lacks a real introduction and Section 2 does not really explain what makes it possible to apply gap amplification in this context (of relaxed LTC). This fact (i.e., that gap amplification is applicable to relaxed LTCs, a notion tailored in the current work) is the main observation of the paper (not the fact that a relaxed LTC can be turned into a strong LTC with parameters as in Observation 2.4).

Note (Jan'17): See added overview on his follow-up work.

The original abstract

See ECCC TR13-022.

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.

In this paper we solve an open question raised by Goldreich and Sudan (J.ACM 2006) and construct binary linear strong LTCs with query complexity 3, constant relative distance, constant soundness and inverse polylogarithmic rate.

Our result is based on the previous paper of the author (Viderman, ECCC TR12-168), which presented binary linear strong LTCs with query complexity 3, constant relative distance, and inverse polylogarithmic soundness and rate. We show that the ``gap amplification'' procedure of Dinur (J.ACM 2007) can be used to amplify the soundness of these strong LTCs from inverse polylogarithmic up to a constant, while preserving the other parameters of these codes.

Back to list of Oded's choices.