Strong LTCs with inverse polylogarithmic rate and soundness

by Michael Viderman

Oded's comments

The introduction explains the issues quite well, but still I will summarize. The main issue is obtaining a strong LTC rather than a weak LTC, where strong LTCs correspond to proximity oblivious testers whereas weak LTCs are even weaker than ordinary testers (i.e., they work for a fixed value of the proximity parameter). The strong LTC obtained in this work does not meet the parameters of the best known LTC; it achieves 1/polylog soundness rather than constant soundness. Still, as explained in the paper (cf. p. 4), a significant first step (in an outlined two-step program) is made, and the second step is left for future work.

The original abstract

See ECCC TR12-168.

An error-correcting code $C \subseteq \F^n$ is called $(q,\epsilon)$-strong locally testable code (LTC) if there exists a randomized algorithm (tester) that makes at most $q$ queries to the input word. This algorithm 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.

A well-known open question in the area of LTCs (Goldreich and Sudan, J.ACM 2006) asks whether exist strong LTCs with constant query complexity, constant soundness and inverse polylogarithmic rate.

In this paper, we construct strong LTCs with query complexity 3, inverse polylogarithmic soundness and inverse polylogarithmic rate.


Back to list of Oded's choices.