Tom Gur
@tomgur.bsky.social
Professor of Computer Science at Cambridge.
A personal note: I might be biased, but Cambridge is a truly magical place. I couldn’t imagine a better place to live and work.
October 7, 2025 at 11:38 AM
A personal note: I might be biased, but Cambridge is a truly magical place. I couldn’t imagine a better place to live and work.
The de-quantization behind this new work strongly relies on the earlier breakthrough of Jop Briët and Davi Castro-Silva (arxiv.org/abs/2505.13134) — their contributions were essential to making this possible.
A near-optimal Quadratic Goldreich-Levin algorithm
In this paper, we give a quadratic Goldreich-Levin algorithm that is close to optimal in the following ways. Given a bounded function $f$ on the Boolean hypercube $\mathbb{F}_2^n$ and any $\varepsilon...
arxiv.org
September 8, 2025 at 4:44 PM
The de-quantization behind this new work strongly relies on the earlier breakthrough of Jop Briët and Davi Castro-Silva (arxiv.org/abs/2505.13134) — their contributions were essential to making this possible.
This was a really fun collaboration with the amazing Srinivasan Arunachalam, Davi Castro-Silva, and Arkopal Dutt. We suspect there is a fundamental connection between additive combinatorics and quantum computing, and it would be interesting to deepen our understanding of it.
September 3, 2025 at 8:48 AM
This was a really fun collaboration with the amazing Srinivasan Arunachalam, Davi Castro-Silva, and Arkopal Dutt. We suspect there is a fundamental connection between additive combinatorics and quantum computing, and it would be interesting to deepen our understanding of it.
This is great! (Reminds me a bit of Irit Dinur’s “Proofs are approximations of our understanding, which we can communicate to others”). I might borrow your analogy next time I teach complexity theory. Thanks for sharing!
July 18, 2025 at 7:43 PM
This is great! (Reminds me a bit of Irit Dinur’s “Proofs are approximations of our understanding, which we can communicate to others”). I might borrow your analogy next time I teach complexity theory. Thanks for sharing!
Excited to have Yiyi in Cambridge next year!
June 11, 2025 at 3:01 PM
Excited to have Yiyi in Cambridge next year!