Strong LTCs with inverse poly-log rate and constant soundness

摘要

An error-correcting code CFn 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 codewords with probability 1 and rejects all non-codewords xC with probability at least (xC) , where (xC) 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 Goldreich 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 (Viderman, 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.