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 slide about Charmin and Kirkland toilet paper
Learning a lot at the first #FOCS2025 Best Student Paper award, by Rahul Ilango!
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
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...
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...
๐ก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!
๐ข 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
I got a lot out of participating in WALDO back in 2021, so I definitely recommend checking it out! ๐
The TCS+ calendar: Tom Gur on March 19 Or Zamir on April 9 Ryan Williams on April 23 Palak Jain on May 7
Bob* your calendar, as they say!
*Mark?
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...
