Shivam Nadimpalli
@shivamnadimpalli.bsky.social
CS Theory postdoc at MIT (https://math.mit.edu/~shivamn)
Reposted by Shivam Nadimpalli
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
November 13, 2025 at 2:59 AM
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...
November 7, 2025 at 4:07 PM
A very exciting result!! arxiv.org/pdf/2511.045...
Reposted by Shivam Nadimpalli
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...
November 5, 2025 at 1:12 AM
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...
Reposted by Shivam Nadimpalli
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
arxiv.org/pdf/2509.02338
September 3, 2025 at 8:48 AM
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
arxiv.org/pdf/2509.02338
Reposted by Shivam Nadimpalli
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...
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
July 31, 2025 at 9:40 PM
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...
It was proven by Upton in 1968.
Before that, nobody knew how to cut pizza.
en.m.wikipedia.org/wiki/Pizza_t...
Reposted by Shivam Nadimpalli
💡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...
- 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...
TCS+ - 2024-2025
2025/04/23: Ryan Williams, "Simulating Time With Square-Root Space"
Ryan Williams (MIT)
sites.google.com
April 30, 2025 at 4:43 AM
💡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...
- 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!
April 23, 2025 at 9:47 PM
The introduction is also extremely fun to read!
Reposted by Shivam Nadimpalli
📢 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
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
April 17, 2025 at 6:17 AM
📢 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
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! 😄
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
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
Workshop on Algorithms for Large Data (Online) 2025
waldo-workshop.github.io
March 19, 2025 at 6:42 PM
I got a lot out of participating in WALDO back in 2021, so I definitely recommend checking it out! 😄
Reposted by Shivam Nadimpalli
Bob* your calendar, as they say!
*Mark?
*Mark?
March 16, 2025 at 7:57 PM
Bob* your calendar, as they say!
*Mark?
*Mark?
I'm a fan of this post!
Accessible TeX colors
Ewin's website
ewintang.com
March 6, 2025 at 3:26 AM
I'm a fan of this post!
Reposted by Shivam Nadimpalli
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!
(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!
February 25, 2025 at 8:57 AM
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!
(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!
Reposted by Shivam Nadimpalli
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!
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!
people.csail.mit.edu
February 21, 2025 at 10:19 PM
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!
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!
Reposted by Shivam Nadimpalli
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...
www.youtube.com/watch?v=726O...
Timothy Gowers, Some recent developments in combinatorics
YouTube video by Clay Mathematics Institute
www.youtube.com
November 19, 2024 at 7:00 PM
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...
www.youtube.com/watch?v=726O...