Tom Gur

The Lens of Abelian Embeddings We discuss a recent line of research investigating inverse theorems with respect to general k-wise correlations, and explain how such correlations arise in different contexts in mathematics. We outlin...

I’ve been enjoying Dor Minzer’s new survey “The Lens of Abelian Embeddings”. It gives a clear, additive-combinatorics-flavoured perspective on inverse theorems for k-wise correlations, with applications in discrete maths/TCS and plenty of open problems. arxiv.org/abs/2602.22183

Postdoctoral Research Associate (Fixed Term) at University of Cambridge Explore an exciting academic career as a Postdoctoral Research Associate (Fixed Term). Don't miss out on other academic jobs. Click to apply and explore more opportunities.

Postdoc position in Cambridge with Julia Wolf:

Julia is a phenomenal researcher and a wonderful collaborator. She is advertising a 2-year postdoc in additive combinatorics and model theory.

Closing date: 16 March. Details: jobs.ac.uk/job/DQP803/postdoctoral-research-associate-fixed-term

The 2nd Quantum Cambridge–Oxford–Warwick (QCOW) Workshop will take place at Warwick on April 23–24. Theme: Quantum Learning Theory. The programme will feature tutorials and accessible in-depth talks on recent advances by leading experts. Speakers/updates:
qcow.cs.ox.ac.uk/

I’m tempted to order it too. Let me know if you enjoy the exposition

Congrats to ToC for having you!

The list of accepted papers at #STOC2026 is out:
acm-stoc.org/stoc2026/acc...

Congratulations to all authors!

Theoretical CS community! I have a small favor to ask. If you ever used, read, watched some of the (excellent IMO) exposition content by Ryan O'Donnell, would you mind filling this very short survey, and maybe say how useful to you it was?

📝 forms.gle/xrvc2mLRbMqK...

Please spread this! #TCSSky

A *very* enthusiastic yes for both!

Thanks for sharing! I would have missed this gem if not for your crisp expository note.

Congrats to Irit Dveer Dinur of the Institute for Advanced Study & Weizmann Insitute, #NASmember Subhash Khot of New York University, Guy Kindler of @hebrewuniversity.bsky.social, Dor Minzer of @mit.edu, and Muli Safra of Tel Aviv University, winners of the 2026 Michael and Sheila Held Prize! (1/2)

ICALP 2026 CFP is out.
This year it’ll be at Royal Holloway (London area), July 7–10, 2026.
Abstract registration: Feb 3
Paper deadline: Feb 6
Details: icalppodcspaa2026.cs.rhul.ac.uk/icalp/

General Relativity - YouTube

I strongly recommend Tobias Osborne's lectures on general relativity. They are full of insight and lots of fun to watch.
www.youtube.com/playlist?lis...

Would you recommend Open World?

Thanks! It depends for which object. For RLDCs, we have this lower bound: eccc.weizmann.ac.il/report/2025/...

For PCPPs and dPCPs, in general that’s a big open problem, but one can view c^3 LTCs as codes augmented with PCPPs.

New paper with the brilliant Dor Minzer, Guy Weissenberg, and Kai Zhe Zheng: we show a separation between RLDCs and LDCs via HDX-based PCPs. This one is special to me; it answers a question Oded Goldreich posed to me in my 1st PhD year, and it’s been on my mind ever since.
arxiv.org/pdf/2512.129...

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!