High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity

Abstract

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 LCCs and LTCs with block length n, constant rate (which can even be taken arbitrarily close to 1) and constant relative distance, whose query complexity is exp(Õ(√logn)) (for LCCs) and (logn)O(loglogn) (for LTCs). Previously such codes were known to exist only with Ω(nβ) query complexity (for constant β>0).