Some initial thoughts, and a complicated mix of feelings. Wow. I mean, Erdos problems are cool (I genuinely mean that), I didn't know about the Jacobian conjecture before it got disproved. But this newest batch from OpenAI hits home in a way the previous announcements did not.

TCS+, the longest-running theoretical #computerscience seminar, will soon resume for the Fall. Let us know what you'd like to hear about (results, speakers, topics), and any suggestions you may have! sites.google.com/view/tcsplus... #TCSSky @tcsplus.bsky.social

An information-theoretic proof of majorizing measures! 😮

Simple and Sharp Generalization Bounds via Lifting

We develop an information-theoretic framework for bounding the supremum of stochastic processes, offering a simpler and sharper alternative to classical chaining and slicing arguments for generalizati...

arxiv.org

Parallel pancakes spotted in the wild (Inman Sq, Cambridge MA)

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

Learning a lot at the first #FOCS2025 Best Student Paper award, by Rahul Ilango!

Wow! 😮

Talagrand's convolution conjecture up to loglog via perturbed reverse heat

We prove that under the heat semigroup $(P_τ)$ on the Boolean hypercube, any nonnegative function $f: \{-1,1\}^n \to \mathbb{R}_+$ exhibits a uniform tail bound that is better than that by Markov's in...

arxiv.org

My student @johnbostanci.bsky.social, Chinmay Nirkhe, Jonas Haferkamp, and Mark Zhandry have put out a tour-de-force paper that shows, relative to a classical oracle, QMA is stronger than QCMA -- i.e., quantum proofs >> classical proofs. Congratulations to the authors! arxiv.org/abs/2511.09551

Separating QMA from QCMA with a classical oracle

We construct a classical oracle proving that, in a relativized setting, the set of languages decidable by an efficient quantum verifier with a quantum witness (QMA) is strictly bigger than those decid...

arxiv.org

A very exciting result!! arxiv.org/pdf/2511.045...

The Zoom link for Aparna's talk on "Quantum One-Time Programs, Revisited" is now available on our website. See you tomorrow, 1pm ET! www.tcsplus.org/welcome/next...

TCS+@tcsplus.bsky.social · 10mo ago

📢 Our third TCS+ talk of the season will be Wednesday, Nov 5 (10am PT, 1pm ET, 19:00 CET): Aparna Gupte, from MIT, will tell us about "Quantum One-Time Programs, Revisited"! RSVP to receive the link (available one day prior to the talk): forms.gle/XWih8Z6Lfspi...

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

Fun facts: the Pizza theorem 🍕 states that if Alice and Bob cut a pizza in 4k slices (for k≥2) and take alternating slices, they'll get the same amount even if the cutting wasn't centered. It was proven by Upton in 1968. Before that, nobody knew how to cut pizza. en.m.wikipedia.org/wiki/Pizza_t...

Pizza theorem - Wikipedia

en.m.wikipedia.org

💡The first talks of the season are available! - Prasanna Ramakrishnan, "How to Appease a Voter Majority" - Or Zamir, "Optimality of Frequency Moment Estimation" - Tom Gur, "A Zero-Knowledge PCP Theorem" - Ryan Williams, "Simulating Time With Square-Root Space" sites.google.com/view/tcsplus...

The introduction is also extremely fun to read!

Clément Canonne@ccanonne.github.io · last yr.

This looks exciting! arxiv.org/abs/2504.160... by Xi Chen, Shyamal Patel, and Rocco Servedio. An exp(k^1/3)-query adaptive algo for tolerant testing of k-juntas ("is a Boolean function on n variables close from depending on only k variables?"), via a connection to agnostic learning conjunctions.

📢 Our fourth TCS+ talk will be Wednesday, April 23 (10amPT, 1pm ET, 19:00 CEST): Ryan Williams (@rrwilliams.bsky.social), from MIT, will tell us about "Simulating Time With Square-Root Space"! RSVP to receive the link (available one day prior to the talk): forms.gle/hi9pBsgjRBMb... #TCSSky

TCS+ RSVP: Ryan Williams (2025/05/23)

Title: Simulating Time With Square-Root Space

forms.gle

I got a lot out of participating in WALDO back in 2021, so I definitely recommend checking it out! 😄

Clément Canonne@ccanonne.github.io · last yr.

An announcement: the Workshop on Algorithms for Large Data (Online) 2025 will take place 🗓️ April 14—16. waldo-workshop.github.io/2025.html Goal: "to generate new collaborations through an emphasis on big data algorithms, broadly defined" Register (free) by ⏰ April 7 to access the virtual platform

Bob* your calendar, as they say! *Mark?

I'm a fan of this post!

Teaser: our first TCS+ of the season will be March 5 by Prasanna Ramakrishnan (Stanford), telling us "How to Appease a Voter Majority." (We'd usually suggest cookies, lots of cookies 🍪 — but it turns out there is a better way!) Mark the data: more details in the days to come!

New paper: Simulating Time With Square-Root Space people.csail.mit.edu/rrw/time-vs-... It's still hard for me to believe it myself, but I seem to have shown that TIME[t] is contained in SPACE[sqrt{t log t}]. To appear in STOC. Comments are very welcome!

There have been several remarkable developments in combinatorics, my field of mathematics. A few weeks ago I gave a talk to a general mathematical audience in which I described six breakthroughs from the last five years. www.youtube.com/watch?v=726O...

Timothy Gowers, Some recent developments in combinatorics

YouTube video by Clay Mathematics Institute

youtube.com