June was a somewhat quiet month for sublinear-time algorithms with only one paper coming to our attention.

Relaxed Local Correctability from Local Testing by Vinayak M. Kumar and Geoffrey Mon (arXiv). As the name indicates, the paper proposes a scheme to construct good relaxed locally correctable codes (RLCC) from good locally testable codes (LTC). A relaxed local decoder for an RLCC is a sublinear algorithm that, given query access to a corrupted word \(w\) of length \(n\) and an index \(i \in [n]\) as input, either returns \(c[i]\), where \(c\) is the closest codeword to \(w\), or returns a failure symbol \(\perp\). In the regime of constant distance and constant rate, the prior best known lower and upper bounds on the query complexity of RLCCs is \(\tilde{\Omega}(\sqrt{\log n})\) (Dall’Agnol, Gur, and Lachish; 2021) and \((\log n)^{O(\log \log \log n)}\) (Cohen and Yankovitz; 2022), respectively. Using their scheme to convert LTCs to RLCCs, this paper improves the state of the art by providing constant distance constant rate RLCCs with query complexity \(\log^{O(1)} n\).