Tom Gur

activity

20122026

most citedOn the Power of Interactive Proofs for Learning

4 citations · 17 across the 23 of their papers we have counts for

collaborators

Showing 2025 · cs.CCShow all

2 papers · 2 filters

cs.CC2025

3-Query RLDCs are Strictly Stronger than 3-Query LDCs

Tom Gur, Dor Minzer, Guy Weissenberg +1

We construct $3$ -query relaxed locally decodable codes (RLDCs) with constant alphabet size and length $O ~ (k^{2})$ for $k$ -bit messages. Combined with the lower bound of $\tild…

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 $q$ -query linear RLDC $C\colon \{0,1\}^k \to \…