Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR12-168 | 26th November 2012 01:13

Strong LTCs with inverse polylogarithmic rate and soundness

RSS-Feed




TR12-168
Authors: Michael Viderman
Publication: 26th November 2012 02:58
Downloads: 3256
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint