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

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

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

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

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

📢 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]

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!

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

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!

Three (!) papers on ECCC today by Derksen, Lee, and Viola, show new results in pseudorandomness, symmetry, smoothing, and boosting uniformity in quasirandom groups. One interesting takeaway is that (even noisy) small bias does not fool several classes of tests better than bounded uniformity. Links:

I've enjoyed this excellent exposition of the recent progress in the combinatorial list-size bounds of Folded Reed Solomon codes and multiplicity codes by Garg, Harsha, Kumar, Saptharishi, and Shankar. A fascinating read. arxiv.org/pdf/2502.143...

I am happy to announce that the Kakeya set conjecture, one of the most sought after open problems in geometric measure theory, has now been proven (in three dimensions) by Hong Wang and Joshua Zahl! arxiv.org/abs/2502.17655 I discuss some ideas of the proof at terrytao.wordpress.com/2025/02/25/t...

Wow!

The #FOCS2025 website is up! Featuring a Call for Papers and important dates: focs.computer.org/2025/ ⏰ Deadline: April 3, 2025 (8pm ET) ⏰ Notification: July 8, 2025 🗓️ Conference: December 14–17, 2025 Content and info will be added as it becomes available (workshops, activities, travel support).

The list of accepted papers for #STOC2025 (h/t @gautamkamath.com) is up! Of course, all papers there are good (TCS confs have many false negatives, seldom false positives), but below 🧵 I'll list a few papers I'm particularly eager to learn more about. Personal taste! acm-stoc.org/stoc2025/acc...

Gil Cohen gave a fabulous mini-course on analytic approaches to spectral graph theory and Ramanujan graphs. Highly recommended! The lectures are available in the link below. www.youtube.com/playlist?lis...

Irit Dinur, Venkat Guruswami and I are organizing a 2-week program on HDX and Codes at ICTS-TIFR, Bengaluru, India. See attached poster for more details and how to apply for the program. www.icts.res.in/program/HDXa...

Here's a deceptively simple probability 🧩, shared with me by Zachary Chase: Throw n balls in k bins independently and uniformly at random. Let p(n,k) be the probability that at least one ball is alone in its bin. Surely, p(n,k) is non-decreasing in k, for fixed n! Can you prove it?

I love this paper by Bill Kuszmaul. His proof of Chernoff bound is much more illuminating than the standard algebraic proof I learned.

I look forward to this event!

What a fantastic initiative! Beyond funding/visa issues, this will also benefit people with family constraints, those concerned about reducing their carbon footprint, and many others. I'm looking forward to the online Junior-Senior Lunch!

Good news for the new year: if you want a more streamlined proof of the landmark result MIP* = RE, then a new paper does that (and much more): arxiv.org/abs/2501.00173 (207 pages, though)

Random d-regular graphs are (2-sided) Ramanujan with probability 69%: arxiv.org/pdf/2412.20263 by Jiaoyang Huang, Theo Mckenzie, HT Yau. In particular, infinitely many 7-regular Ramanujan graphs exist.

Relaying a message: some TCS people (initiative led by Hanlin Ren) are setting up an online version of ITCS'25, for those who are not able to attend in person this January. Format and details TBD, but if you're potentially interested, fill this form: forms.gle/RPHRC6R331bH... #TCSSky

An advent calendar of some of my favourite TCS/Maths talks. Day #1: Avi Wigderson on Reading Alan Turing. It is a gem of a talk, full of insights about Turing's work, writing style, and influences on mathematics and computer science. Pure joy! www.youtube.com/watch?v=_Uk_...

A few days ago Lawrence Hollom posted a preprint that solves a problem about posets, informally known as the fishbone conjecture, which I am told was extremely central in the area. 🧵 arxiv.org/abs/2411.16844

Bhangale, Khot, Liu, and Minzer improved the bounds for combinatorial lines of length 3, established in the Polymath project on the Hales-Jewett problem. Interestingly, this is done from a TCS perspective using pseudorandomness and inverse theorems for CSPs. eccc.weizmann.ac.il/report/2024/...

Just created a Quantum Computing Starter Pack. Please reach out if I missed to add you. go.bsky.app/KBgRwmZ

I don't know if this is any different, but I made it into a "starter pack" in case that's helpful: go.bsky.app/6A6GRSi