Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR10-171 | 11th November 2010 17:59

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

TR10-171
Authors: Michael Viderman
Publication: 11th November 2010 18:46
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