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