Search for: All records

Locally testable codes (LTC) are error-correcting codes that have a local tester which can distinguish valid codewords from words that are far from all codewords, by probing a given word only at a very small (sublinear, typically constant) number of locations. Such codes form the combinatorial backbone of PCPs. A major open problem is whether there exist LTCs with positive rate, constant relative distance and testable with a constant number of queries. In this paper, we present a new approach towards constructing such LTCs using the machinery of high-dimensional expanders. To this end, we consider the Tanner representation of a code, which is specified by a graph and a base code. Informally, our result states that if this graph is part of an {\em agreement expander} then the local testability of the code follows from the local testability of the base code. Agreement expanders allow one to stitch together many mostly-consistent local functions into a single global function. High-dimensional expanders are known to yield agreement expanders with constant degree. This work unifies and generalizes the known results on testability of the Hadamard, Reed-Muller and lifted codes, all of which are proved via a single round of local self-correction: the corrected value at a vertex v depends on the values of all vertices that share a constraint with v. In the above codes this set includes all of the vertices. In contrast, in our setting the degree of a vertex might be a constant, so we cannot hope for one-round self-correction. We overcome this technical hurdle by performing iterative self correction with logarithmically many rounds and tightly controlling the error in each iteration using properties of the agreement expander. Given this result, the missing ingredient towards constructing a constant-query LTC with positive rate and constant relative distance is an instantiation of a base code and a constant-degree agreement expander that interact well with each other.