Tom Gur

Reminder: Two weeks left to apply for the Assistant/Associate Professor positions in Theoretical Computer Science at Cambridge.

Application deadline: 15 December 2025.

Details and application portal:
cst.cam.ac.uk/assistantass...

Wow! Yuansi Chen resolves 1 of the 2 remaining $1000 Talagrand problems (michel.talagrand.net/prizes/prize... ):

If you take any f : {-1,+1}ⁿ → ℝ⁺ and apply the noise operator T_{.99}, the resulting function g = T_{.99} f satisfies a better-than-Markov inequality. That is, Pr[g > t E[g]] < o(1/t).

A new paper with the brilliant Guy Goldberg and Sidhant Saraogi (now on the job market!). We prove nearly tight lower bounds for relaxed LDCs via a new combinatorial notion of relaxed sunflowers with pseudorandom structure, obtained from new spread lemmas.

eccc.weizmann.ac.il/report/2025/...

Join us for the first Quantum Cambridge–Oxford–Warwick Colloquium (Quantum COW, if you insist...), 11–12 December 2025 at the University of Oxford.

This meeting focuses on Quantum Low-Depth Complexity, with talks, tutorials, and open discussions.

Details: qcow.cs.ox.ac.uk

Reminder: the School of Computer Science at #USyd is hiring across the board, equiv. tenure-track positions!

Join us at @sydney.edu.au! Deadline ⏰ December 1 🇦🇺

The list of accepted papers for #QIP2026 is now online at qip2026.lu.lv/programme/ac...

The inaugural Computational Complexity Conference Test of Time Award seeks nominations (deadline Monday, March 2, 2026). Help us select an awesome paper for this award!

computationalcomplexity.org/tot/tot26.html

I’m looking for postdocs and PhD students to join my group at Cambridge!

Topics include: Classical & Quantum Complexity, Sublinear Algorithms, Coding Theory, Cryptography, Learning Theory, and their interplay with Fourier Analysis & Additive Combinatorics.

To apply or inquire, email me your CV.

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.&nbsp; 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!