We prove a nearly optimal lower bound on the blocklength of general relaxed locally decodable codes (RLDCs), extending the result of [GGS26] to nonlinear encodings and adaptive decoders with two-sided error. Namely, we show that any $q$-query RLDC $C\colon \{0,1\}^k \to \{0,1\}^n$ must satisfy $n = k^{1+\Omega(1/q)}$, closely matching the ... more >>>

A tester decides whether a graph has a property or is far from having it. A distance estimator asks for more: it must approximately determine how many edges need to be changed. A property is said to be testable if there is a tester with a number of queries bounded ... more >>>

We prove that any linear $3$-query locally correctable code $C \colon \mathbb{F}_2^k \to \mathbb{F}_2^n$ with constant correction radius must have length $n \geq 2^{\Omega(\sqrt{k})}$. This improves on the prior best lower bound of $2^{\Omega(\sqrt{k/\log k})}$, due to [AG24], and shows that the folklore construction of linear $3$-LCCs from Reed--Muller codes, ... more >>>