A Note on high-rate Locally Testable Codes with sublinear query complexity
Michael Viderman · Electronic colloquium on computational complexity · 2010
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 ; > 0 there exists a family of LTCs over the binary field with query complexity n and rate at least 1 . To obtain this construction we use the result of Ben-Sasson and Viderman (2009).