Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR10-171 | 11th November 2010 17:59

A Note on high-rate Locally Testable Codes with sublinear query complexity

RSS-Feed




TR10-171
Authors: Michael Viderman
Publication: 11th November 2010 18:46
Downloads: 3220
Keywords: 


Abstract:

Inspired by recent construction of high-rate locally correctable codes with sublinear query complexity due to
Kopparty, Saraf and Yekhanin (2010) we address the similar question for locally testable codes (LTCs).

In this note we show a construction of high-rate LTCs with sublinear query complexity.
More formally, we show that for every $\epsilon, \rho > 0$ there exists a family of LTCs over the binary field with query complexity $n^{\epsilon}$ and rate at least $1-\rho$.
To obtain this construction we use the result of Ben-Sasson and Viderman (2009).



ISSN 1433-8092 | Imprint