Ryan O'Donnell
@booleananalysis.bsky.social
Reposted by Ryan O'Donnell
The Call for Papers for #STOC2027 is up! Importantly, the PC "will place substantial weight on the quality of exposition, and clarity of technical arguments and proofs"
Also:
- Public posting requirement
- Required video submission
and more.
Deadline: ⏰ Nov 2, AoE
acm-stoc.org/stoc2027/sto...
Also:
- Public posting requirement
- Required video submission
and more.
Deadline: ⏰ Nov 2, AoE
acm-stoc.org/stoc2027/sto...
September 17, 2026 at 7:56 PM
The Call for Papers for #STOC2027 is up! Importantly, the PC "will place substantial weight on the quality of exposition, and clarity of technical arguments and proofs"
Also:
- Public posting requirement
- Required video submission
and more.
Deadline: ⏰ Nov 2, AoE
acm-stoc.org/stoc2027/sto...
Also:
- Public posting requirement
- Required video submission
and more.
Deadline: ⏰ Nov 2, AoE
acm-stoc.org/stoc2027/sto...
Reposted by Ryan O'Donnell
Sahil Singla: The Matroid Secretary Conjecture is True https://arxiv.org/abs/2609.14555 https://arxiv.org/pdf/2609.14555 https://arxiv.org/html/2609.14555
September 15, 2026 at 6:41 AM
Sahil Singla: The Matroid Secretary Conjecture is True https://arxiv.org/abs/2609.14555 https://arxiv.org/pdf/2609.14555 https://arxiv.org/html/2609.14555
Outstanding progress towards the Unique Games Conjecture posted by Yumou Fei, Dor Minzer, and Shuo Wang: eccc.weizmann.ac.il/report/2026/...
👀
👀
ECCC - TR26-179
eccc.weizmann.ac.il
September 14, 2026 at 6:34 PM
Outstanding progress towards the Unique Games Conjecture posted by Yumou Fei, Dor Minzer, and Shuo Wang: eccc.weizmann.ac.il/report/2026/...
👀
👀
Am teaching grad complexity theory at CMU; about 1/3 of the lectures will be new (vs. last time), 'modern' results. Videos are going onto www.youtube.com/@ComplexityT... which will later also feature student videos.
We did Williams (/Cook-Mertz/Shalunov) TIME(t) in SPACE(~√t) today.
We did Williams (/Cook-Mertz/Shalunov) TIME(t) in SPACE(~√t) today.
Complexity Theory At Carnegie Mellon
www.youtube.com
September 10, 2026 at 6:18 PM
Am teaching grad complexity theory at CMU; about 1/3 of the lectures will be new (vs. last time), 'modern' results. Videos are going onto www.youtube.com/@ComplexityT... which will later also feature student videos.
We did Williams (/Cook-Mertz/Shalunov) TIME(t) in SPACE(~√t) today.
We did Williams (/Cook-Mertz/Shalunov) TIME(t) in SPACE(~√t) today.
I gave a talk at Carnegie Mellon about the recent proof (by OpenAI) of the existence of a non-sofic group:
youtu.be/uOQvzLjJK6c
youtu.be/uOQvzLjJK6c
A non-sofic group
YouTube video by Ryan O'Donnell
youtu.be
September 4, 2026 at 3:13 AM
I gave a talk at Carnegie Mellon about the recent proof (by OpenAI) of the existence of a non-sofic group:
youtu.be/uOQvzLjJK6c
youtu.be/uOQvzLjJK6c
Reposted by Ryan O'Donnell
Since today Bipartite Perfect Matching is in NC. The proof uses connections between coding theory and Hall's theorem. Presented at WACT 2026. Yay!!!
June 4, 2026 at 12:37 PM
Since today Bipartite Perfect Matching is in NC. The proof uses connections between coding theory and Hall's theorem. Presented at WACT 2026. Yay!!!
FOCS 2026 Test of Time call for nominations is out:
tc.computer.org/tcmf/2026/05...
Please submit your nominations! More info on the award here:
tc.computer.org/tcmf/focs-te...
and here's DBLP links for FOCS '16, '06, '96:
dblp.org/db/conf/focs...
dblp.org/db/conf/focs...
dblp.org/db/conf/focs...
tc.computer.org/tcmf/2026/05...
Please submit your nominations! More info on the award here:
tc.computer.org/tcmf/focs-te...
and here's DBLP links for FOCS '16, '06, '96:
dblp.org/db/conf/focs...
dblp.org/db/conf/focs...
dblp.org/db/conf/focs...
May 18, 2026 at 7:56 PM
FOCS 2026 Test of Time call for nominations is out:
tc.computer.org/tcmf/2026/05...
Please submit your nominations! More info on the award here:
tc.computer.org/tcmf/focs-te...
and here's DBLP links for FOCS '16, '06, '96:
dblp.org/db/conf/focs...
dblp.org/db/conf/focs...
dblp.org/db/conf/focs...
tc.computer.org/tcmf/2026/05...
Please submit your nominations! More info on the award here:
tc.computer.org/tcmf/focs-te...
and here's DBLP links for FOCS '16, '06, '96:
dblp.org/db/conf/focs...
dblp.org/db/conf/focs...
dblp.org/db/conf/focs...
Reposted by Ryan O'Donnell
Congratulations to Charles H. Bennett and Gilles Brassard on receiving the 2025 ACM A.M. Turing Award! They are recognized for their essential role in establishing the foundations of quantum information science and transforming secure communication and computing. awards.acm.org/turing @umontreal
March 18, 2026 at 9:01 AM
Congratulations to Charles H. Bennett and Gilles Brassard on receiving the 2025 ACM A.M. Turing Award! They are recognized for their essential role in establishing the foundations of quantum information science and transforming secure communication and computing. awards.acm.org/turing @umontreal
Very inspiring and poignant talk by the great John Watrous on (quantum) education at QIP2026.
(Check out the video when it's available, or his quantum course youtube.com/playlist?lis... while you wait.)
(Check out the video when it's available, or his quantum course youtube.com/playlist?lis... while you wait.)
January 28, 2026 at 8:05 AM
Very inspiring and poignant talk by the great John Watrous on (quantum) education at QIP2026.
(Check out the video when it's available, or his quantum course youtube.com/playlist?lis... while you wait.)
(Check out the video when it's available, or his quantum course youtube.com/playlist?lis... while you wait.)
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).
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).
November 25, 2025 at 4:16 PM
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).
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).
Kewen Wu on "No exponential quantum speedup for SIS∞ anymore"...
Or if you prefer a special case, "Subset-Sum with vectors mod 3":
www.youtube.com/watch?v=Pl2b...
Or if you prefer a special case, "Subset-Sum with vectors mod 3":
www.youtube.com/watch?v=Pl2b...
No Exponential Quantum Speedup for SIS^inf Anymore - Kewen Wu
YouTube video by Institute for Advanced Study
www.youtube.com
November 5, 2025 at 2:42 AM
Kewen Wu on "No exponential quantum speedup for SIS∞ anymore"...
Or if you prefer a special case, "Subset-Sum with vectors mod 3":
www.youtube.com/watch?v=Pl2b...
Or if you prefer a special case, "Subset-Sum with vectors mod 3":
www.youtube.com/watch?v=Pl2b...
Reposted by Ryan O'Donnell
Congratulations to Venkat Guruswami, new director of the Simons Institute for the Theory of Computing (@simonsinstitute.bsky.social)! And congrats to us, the Theoretical CS community, for having someone as good, dedicated, and wonderful as him at the helm of a place so important to us! #TCSSky
October 30, 2025 at 8:18 PM
Congratulations to Venkat Guruswami, new director of the Simons Institute for the Theory of Computing (@simonsinstitute.bsky.social)! And congrats to us, the Theoretical CS community, for having someone as good, dedicated, and wonderful as him at the helm of a place so important to us! #TCSSky
October 11, 2025 at 1:07 PM
Reposted by Ryan O'Donnell
Feeling depressed and anxious about the state of the world? Try working on a 375 year-old math problem from the Platonic realm, which should be completely psychologically safe . . .
youtu.be/QH4MviUE0_s
youtu.be/QH4MviUE0_s
Rupert's Snub Cube and other Math Holes
YouTube video by suckerpinch
youtu.be
September 16, 2025 at 2:23 PM
Feeling depressed and anxious about the state of the world? Try working on a 375 year-old math problem from the Platonic realm, which should be completely psychologically safe . . .
youtu.be/QH4MviUE0_s
youtu.be/QH4MviUE0_s
Please take a minute and nominate your favourite paper from FOCS 1995, 2005, or 2015 for the FOCS Test Of Time Award!
1995 papers: dblp.org/db/conf/focs...
2005 papers: dblp.org/db/conf/focs...
2015 papers: dblp.org/db/conf/focs...
Nomination instructions here:
tc.computer.org/tcmf/2025/08...
1995 papers: dblp.org/db/conf/focs...
2005 papers: dblp.org/db/conf/focs...
2015 papers: dblp.org/db/conf/focs...
Nomination instructions here:
tc.computer.org/tcmf/2025/08...
FOCS Test of Time Award - Call for Nominations 2025 - IEEE Computer Society Technical Committee on Mathematical Foundations of Computing
FOCS 2025 Test of Time Awards Call for Nominations The 2025 FOCS Test of Time Awards, awarded annually, recognize papers published in the Proceedings of the Annual IEEE Symposium on Foundations of...
tc.computer.org
August 26, 2025 at 3:47 PM
Please take a minute and nominate your favourite paper from FOCS 1995, 2005, or 2015 for the FOCS Test Of Time Award!
1995 papers: dblp.org/db/conf/focs...
2005 papers: dblp.org/db/conf/focs...
2015 papers: dblp.org/db/conf/focs...
Nomination instructions here:
tc.computer.org/tcmf/2025/08...
1995 papers: dblp.org/db/conf/focs...
2005 papers: dblp.org/db/conf/focs...
2015 papers: dblp.org/db/conf/focs...
Nomination instructions here:
tc.computer.org/tcmf/2025/08...
Reposted by Ryan O'Donnell
NSF announces funding for ICARM: the Institute for Computer-Aided Reasoning in Mathematics, based in Carnegie-Mellon . Amazing! Carnegie-Mellon press release here: www.cmu.edu/news/stories...
www.nsf.gov/news/nsf-inv...
www.nsf.gov/news/nsf-inv...
NSF invests over $74 million in 6 mathematical sciences research institutes
The U.S. National Science Foundation is investing over $74 million in six research institutes focused on the mathematical sciences and their broad applications in all fields of science, technology and...
www.nsf.gov
August 4, 2025 at 3:22 PM
NSF announces funding for ICARM: the Institute for Computer-Aided Reasoning in Mathematics, based in Carnegie-Mellon . Amazing! Carnegie-Mellon press release here: www.cmu.edu/news/stories...
www.nsf.gov/news/nsf-inv...
www.nsf.gov/news/nsf-inv...
Reposted by Ryan O'Donnell
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
arxiv.org/abs/2507.11536
Understanding Quantum Information and Computation
This is a course on the theory of quantum computing. It consists of 16 lessons, each with a video and written component, covering the basics of quantum information, quantum algorithms (including query...
arxiv.org
July 16, 2025 at 11:06 AM
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
arxiv.org/abs/2507.11536
Reposted by Ryan O'Donnell
New work with @booleananalysis.bsky.social! We prove instance-optimal bounds for quantum state certification when testers can measure all copies simultaneously, finding that the optimal copy complexity depends on how close to maximally mixed the hypothesis state is.
arxiv.org/abs/2507.06010
1/3
arxiv.org/abs/2507.06010
1/3
July 9, 2025 at 2:15 PM
New work with @booleananalysis.bsky.social! We prove instance-optimal bounds for quantum state certification when testers can measure all copies simultaneously, finding that the optimal copy complexity depends on how close to maximally mixed the hypothesis state is.
arxiv.org/abs/2507.06010
1/3
arxiv.org/abs/2507.06010
1/3
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.)
cs.unibocconi.eu/call-nominat...
(Intent-to-nominate letters due by July 31.)
cs.unibocconi.eu
June 9, 2025 at 12:46 PM
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.)
cs.unibocconi.eu/call-nominat...
(Intent-to-nominate letters due by July 31.)
Sigbovik's looking good this year. Come for the tom7/suckerpinch video preview, stay for Shor vs a random number generator...
For sigbovik, I factored all 8 bit ints (up to 255) with a quantum computer github.com/strilanc/fal...
I did it as legit as I possibly could. I ran a correct circuit with no optimization shenanigans. I did correct pre/postprocessing.
It took 121 quantum samples to finish the entire task.
But...
I did it as legit as I possibly could. I ran a correct circuit with no optimization shenanigans. I did correct pre/postprocessing.
It took 121 quantum samples to finish the entire task.
But...
April 2, 2025 at 11:24 AM
Sigbovik's looking good this year. Come for the tom7/suckerpinch video preview, stay for Shor vs a random number generator...
Reposted by Ryan O'Donnell
#STOC2025 (June 23-27, Prague) Theory Fest is looking for workshop proposals. The deadline is March 9th.
Apply here: stoc2025theoryfest.netlify.app
Apply here: stoc2025theoryfest.netlify.app
Vite + React + TS
stoc2025theoryfest.netlify.app
February 27, 2025 at 12:51 PM
#STOC2025 (June 23-27, Prague) Theory Fest is looking for workshop proposals. The deadline is March 9th.
Apply here: stoc2025theoryfest.netlify.app
Apply here: stoc2025theoryfest.netlify.app
Reposted by Ryan O'Donnell
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!