From the 1 of 14 linked papers with an AI index.
2 citations · 3 across the 4 of their papers we have counts for
5 papers · 1 filter
3-Query RLDCs are Strictly Stronger than 3-Query LDCs
Tom Gur, Dor Minzer, Guy Weissenberg +1
We construct -query relaxed locally decodable codes (RLDCs) with constant alphabet size and length for -bit messages. Combined with the lower bound of $\tild…
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 \…
Symmetric quantum computation
Davi Castro-Silva, Tom Gur, Sergii Strelchuk
We introduce a systematic study of "symmetric quantum circuits", a new restricted model of quantum computation that preserves the symmetries of the problems it solves. This model i…
Algorithmic Polynomial Freiman-Ruzsa Theorems
Srinivasan Arunachalam, Davi Castro-Silva, Arkopal Dutt +1
We prove algorithmic versions of the polynomial Freiman-Ruzsa theorem of Gowers, Green, Manners, and Tao (Annals of Mathematics, 2025) in additive combinatorics. In particular, we…
Quantum Communication Advantage in TFNP
Mika Göös, Tom Gur, Siddhartha Jain +1
We exhibit a total search problem with classically verifiable solutions whose communication complexity in the quantum SMP model is exponentially smaller than in the classical two-w…