Strong LTCs with Inverse Poly-Log Rate and Constant Soundness

摘要

An error-correcting code C is called (q, ε)-strong locally testable code (LTC) if there exists a tester that makes at most q queries to the input word. This tester accepts all code words with probability 1 and rejects all non-code words x with probability at least ε · δ(x, C), where δ(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 ε is called soundness. In this paper we resolve an open question raised by Gold Reich and Sudan (J. ACM 2006) and construct binary linear strong LTCs with query complexity 3, constant relative distance, constant soundness and inverse polylogarithmic rate. Our result is based on the previous paper of the author (Vide man, ECCC TR12-168), which presented binary linear strong LTCs with query complexity 3, constant relative distance, and inverse polylogarithmic soundness and rate. We show that the "gap amplification" procedure of Dinur (J. ACM 2007) can be used to amplify the soundness of these strong LTCs from inverse polylogarithmic up to a constant, while preserving the other parameters of these codes. Furthermore, we show that under a conceivable conjecture, there exist asymptotically good strong LTCs with poly-log query complexity.