Strong LTCs with Inverse Polylogarithmic Rate and Soundness

An error-correcting code C ⊆ Fⁿ 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 x ∉ C 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. A well-known open question in the area of LTCs (Goldreich and Sudan, J.ACM 2006) asks whether there 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.