In this work, we construct the first locally-correctable codes (LCCs), and locally-testable codes (LTCs) with constant rate, constant relative distance, and sub-polynomial query complexity. Specifically, we show that there exist binary LCCs and LTCs with block length n , constant rate (which can even be taken arbitrarily close to 1), constant relative distance, and query complexity exp ( O ( log n )) . Previously such codes were known to exist only with ( n ) query complexity (for constant 0"> 0 ), and there were several, quite different, constructions known.

Our codes are based on a general distance-amplification method of Alon and Luby~\cite{AL96_codes}. We show that this method interacts well with local correctors and testers, and obtain our main results by applying it to suitably constructed LCCs and LTCs in the non-standard regime of \emph{sub-constant relative distance}.

Along the way, we also construct LCCs and LTCs over large alphabets, with the same query complexity exp ( O ( log n )) , which additionally have the property of approaching the Singleton bound: they have almost the best-possible relationship between their rate and distance. This has the surprising consequence that asking for a large alphabet error-correcting code to further be an LCC or LTC with exp ( O ( log n )) query complexity does not require any sacrifice in terms of rate and distance! Such a result was previously not known for any o ( n ) query complexity.

Our results on LCCs also immediately give locally-decodable codes (LDCs) with the same parameters.