Bounds on 2-query Locally Testable Codes with affine tests

Research output: Contribution to journalArticlepeer-review

Abstract

We study Locally Testable Codes (LTCs) that can be tested by making two queries to the tested word using an affine test. That is, we consider LTCs over a finite field double-struck F, with codeword testers that only use tests of the form avi+bvj = c, where v is the tested word and a,b,c ∈ double-struck F. We show that such LTCs, with high minimal distance, must be of constant size. Specifically, we show that every 2-query LTC with affine tests over double-struck F, that has minimal distance at least 9/10, completeness at least 1 -ϵ, and soundness at most 1 - 3ϵ, is of size at most |double-struck F|. Our main motivation in studying LTCs with affine tests is the Unique Games Conjecture (UGC), and the close connection between LTCs and PCPs. We mention that all known PCP constructions use LTCs with corresponding properties as building blocks, and that many of the LTCs used in PCP constructions are affine. Furthermore, the UGC was shown to be equivalent to the UGC with affine tests [13], thus the UGC implies the existence of a low-error 2-query PCP with affine tests. We note, however, that our result has no implication on the correctness of the UGC.

Original languageEnglish (US)
Pages (from-to)521-525
Number of pages5
JournalInformation Processing Letters
Volume116
Issue number8
DOIs
StatePublished - Aug 1 2016
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Keywords

  • Computational complexity
  • Locally Testable Codes
  • Theory of computation
  • Unique Games Conjecture

Fingerprint

Dive into the research topics of 'Bounds on 2-query Locally Testable Codes with affine tests'. Together they form a unique fingerprint.

Cite this