Strong LTCs with inverse polylogarithmic rate and soundness

摘要

An error-correcting code CFn is called (q) -strong locally testable code (LTC) if there exists a randomized algorithm (tester) that makes at most q queries to the input word. This algorithm 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.A well-known open question in the area of LTCs (Goldreich and Sudan, J.ACM 2006) asks whether exist strong LTCs with constant query complexity, constant soundness and inverse polylogarithmic rate.In this paper, we construct strong LTCs with query complexity 3, inverse polylogarithmic soundness and inverse polylogarithmic rate.