Tom Gur

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.

Cambridge is recruiting Assistant/Associate Professors in Theoretical Computer Science. #TCS #AcademicJobs

Application deadline: 15 December 2025. Contact me for informal inquiries. See more details and apply here:
www.cst.cam.ac.uk/assistantass...

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...

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.

New arXiv preprint: we show algorithmic versions of the polynomial Freiman–Ruzsa (PFR) theorem of Gowers, Green, Manners, and Tao. Interestingly, our proof draws on quantum information and stabilizer learning algorithms, which we dequantize into classical algorithms.

arxiv.org/pdf/2509.02338

The submission server for #ITCS2026 (which will take place at Bocconi University, Milan, in January 2026) is open!

Submission deadline: Sep 4 (abstracts), Sep 6 (papers)

itcs-conf.org

Paul is a phenomenal researcher, and Oxford is lots of fun. Highly recommended!

The QIP 2026 call for papers is out! QIP 2026 will be held in Riga, Latvia from January 24–30, 2026. See you there!
qip2026.lu.lv

QIP2025

#Quantum #QIP2025
The team @qip2025.bsky.social has uploaded the QIPv2025 talks

www.youtube.com/@QIP2025

Enjoy rewatching your favorites!

New post on the Learning Theory Alliance blog, by Arsen Vasilyan. This covers the recently introduced testable learning paradigm of Rubinfeld and Vasilyan, from their STOC 2023 paper. A great chance to catch up on all the exciting work that's happened in this area!
www.let-all.com/blog/2025/07...

Hirahara, Illango, and Loff posted on the arXiv a lovely result, showing that determining the communication complexity of a function f is NP-hard. A fundamental question first asked by Yao in '79. The proof is very clean and elegant. A fun read for the weekend!

arxiv.org/pdf/2507.104...

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!

Understanding Quantum Information and Computation This is a course on the theory of quantum computing. It consists of 16 lessons, each with a video and written component, covering the basics of quantum information, quantum algorithms (including query...

After 3 1/2 years of work my course on quantum computing is finally finished — the "Director's Cut" of Understanding Quantum Information and Computation is now available.

arxiv.org/abs/2507.11536

YouTube video by Sydney Mathematical Research Institute - SMRI Clément Canonne: What is deterministic amplification?

Recently came across this fantastic talk by @ccanonne.github.io on deterministic amplification via expander graphs—elegant ideas, crystal-clear exposition. A real gem!

www.youtube.com/watch?v=3AAU...

Excited to have Yiyi in Cambridge next year!

Spread the word: there is a new prize in Theoretical Computer Science in honor of Luca Trevisan--

cs.unibocconi.eu/call-nominat...

(Intent-to-nominate letters due by July 31.)

The 2025 Gödel Prize is given to Eshan Chattopadhyay and David Zuckerman, “Explicit two-source extractors and resilient functions”.

Paper: doi.org/10.4007/anna...

Favorite Theorems Blog Post: blog.computationalco...

#STOC2025 "will feature an online poster session, designed to engage both in-person attendees and members of the broader community who are unable to attend the conference physically."

(Initiative led by @iwmertz.bsky.social, Ninad Rajgopal, and @h4n1in.bsky.social)

acm-stoc.org/stoc2025/cal...

TCS+ RSVP: Irit Dinur (2025/06/04) Title: Agreement Tests: Local Consistency, Global Structure

📢 Our sixth and last TCS+ talk of the season will be Wednesday, June 4 (10amPT, 1pm ET, 19:00 CEST): Irit Dinur, from the IAS, will tell us about "Agreement Tests: Local Consistency, Global Structure"!

RSVP to receive the link (available one day prior to the talk):
forms.gle/GJt74TequURy... #TCSSky

Teaser: our last TCS+ of the season will be next week, with Irit Dinur (IAS) on "Agreement Tests: Local Consistency, Global Structure." What a way to conclude the semester!

[More details coming soon to a BlueSky near you]

Quantum Algorithms Researcher - Riverlane Cambridge, UK | Full-time or Part-time | Permanent | HybridSalary: £55,000 to £80,000 DOEThe salary range for this role is broad as we are able to consider varying levels of experience.  Any offe...

We have an open rolling advert for QEC researchers at Riverlane. And now also have a single post to fill for an (error-corrected) algorithms researcher

apply.workable.com/riverlane/j/...

This is such a good one-sentence (albeit a long one…) explanation of quantum computing!

Thanks, Clément! You are too kind!

Definitely exciting! It would be great to have a TCS+ talk about it

The recordings of two courses from the school Complexity as a Kaleydoscope are out: www.carmin.tv/en/c/1642

Antonina's lectures are great, and I was surprised how much I learned from Richard's lectures on Quantum Complexity theory (since I work on the field). I strongly recommend them

YouTube video by Institute for Advanced Study Sylvester, Gallai and Friends: Discrete Geometry Meets Computational Complexity - Avi Wigderson

Sylvester, Gallai and Friends: Discrete Geometry Meets Computational Complexity — a fantastic new talk by Avi Wigderson about Sylvester–Gallai theorems and their connections to Computer Science.

youtu.be/VJ-d1jPc1YM?...

Prakash Murali and I are seeking to jointly recruit a postdoctoral researcher (Dowling postdoctoral fellow) at Cambridge focused on quantum algorithms, complexity, error correction, and architecture.

Further details: www.jobs.cam.ac.uk/job/50485/

Deadline: 7 April 2025

I am very much looking forward to giving this talk at TCS+, which is one of my favourite seminars. Thanks for inviting me!

What are some recommended resources to get into algebraic complexity theory? Any recommendations for video lectures, lecture notes, surveys, or books would be much appreciated.

The next few talks on TCS+ (@tcsplus.bsky.social):
🍰 Tom Gur on Zero-Knowledge PCPs (March 19) (@tomgur.bsky.social)
🍰 Or Zamir on streaming and optimal F₂ moment estimation (April 9)
🍰 Ryan Williams on time v. memory (April 23) (@rrwilliams.bsky.social)

Sweet!