Relaxed Local Correctability from Local Testing

Vinayak M. Kumar, Geoffrey Mon

We construct the first asymptotically good relaxed locally correctable codes with polylogarithmic query complexity, bringing the upper bound polynomially close to the lower bound o…