collaborators

1 paper

cs.CC2025

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

Guy Goldberg, Tom Gur, Sidhant Saraogi

We show a nearly optimal lower bound on the length of linear relaxed locally decodable codes (RLDCs). Specifically, we prove that any -query linear RLDC $C\colon \{0,1\}^k \to \…