Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR25-192 | 24th November 2025 18:54

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

RSS-Feed

Abstract:

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\colon \{0,1\}^k \to \{0,1\}^n$ must satisfy $n = k^{1+\Omega(1/q)}$. This bound closely matches the known upper bound of $n = k^{1+O(1/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.



ISSN 1433-8092 | Imprint