Nearly Tight Lower Bounds for Relaxed Locally Decodable Codes via Robust Daisies

We show a nearly optimal lower bound on the length of linear relaxed locally decodable codes (RLDCs). Specifically, we prove that any $q$-query linear RLDC $C\text{\hspace{0.17em}⁣}:\{0,1{\}}^k\to \{0,1{\}}^n$ must satisfy $n=k^{1+\mathrm{\Omega }(1\mathrm{/}q)}$. This bound closely matches the known upper bound of $n=k^{1+O(1\mathrm{/}q)}$ by Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan (STOC 2004). Our proof introduces the notion of robust daisies, which are relaxed sunflowers with pseudorandom structure, and leverages a new spread lemma to extract dense robust daisies from arbitrary distributions.