@BooleanAnalysis

Videos: https://xitter.cf/t.co/vy9r4V6aOZ

 Pittsburgh, PA
cs.cmu.edu/~odonnell/
Joined October 2011
  • Tweets742
  • Following0
  • Followers7.7K
234Media
I'm releasing a series of videos called "Quantum Computer Programming in 100 Easy Lessons". youtube.com/playlist?list=PL… It will cover the 'usual' content (...CHSH, Grover, Factoring), but with some expositional innovations that I *hope* will make it easier for beginners.
25
1
150
17,182
Ryan O'Donnell retweeted
Ola Svensson
@AlgoSvenssonOct 15
Happy to share that our better-than-2 approximation results for k-median are now on arXiv: arxiv.org/abs/2610.18144 arxiv.org/abs/2610.17172 It has been a pleasure working with this fantastic group: @rares_buhai , Vincent Cohen-Addad, Henry Fleischmann, @anupamg , Antoni "Toni" Jubés Monforte, Madhusudhan Reddy Pittu, @mstou73, and @LukasBirdyy A special shout-out to Toni, who started working on this problem for his Master's thesis almost two years ago. His work led to the impressive analysis of the factor-revealing LP! Now on to other things...

A Better-than-2 Approximation for k-Median Part I: The Power of...

The Greedy algorithm of Jain, Mahdian, Markakis, Saberi, and Vazirani was the best Lagrangian-multiplier-preserving (LMP) approximation algorithm for facility location, and thus the engine behind...

arxiv.org
Ola Svensson
@AlgoSvenssonOct 7
OpenAI completely solved a problem on which my students have worked hard for 1+ years and made significant progress. They should be proud to have pushed on a problem appearing in this historic list of ~400 results. We’ll soon upload our different algorithmic approach to k-median.
2
13
1
108
7,504
I looked forward to this cleanup! Nikloai Chukhin (eccc.weizmann.ac.il/report/2…) significantly cleans and extends the OpenAI 2^(ω(sqrt(n))) lower bound for depth-3 circuits: The (4n-1)-bit function sum_ij a_{i+j}x_iy_j mod 2 needs depth-d circuits of size 2^(Ω~(n log n)^{1/(d-1)}).
1
8
68
6,803
Sorry for spelling @buyolitsez2's name wrong; obviously it is 'Nikolai'.
2
6
789
Ryan O'Donnell retweeted
Anthony Leverrier@letonyoOct 6
this is great: a unified and transparent exposition of the recent breakthroughs on the decoding of Reed-Solomon codes. eccc.weizmann.ac.il/report/2…
5
1
32
4,885
The what now?! arxiv.org/abs/2610.06783v1

Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in...

We give the first polynomial improvements over the textbook algorithms for $3$SUM and All-Pairs Shortest Paths (APSP): we show how to deterministically solve $3$SUM on $n$ integers of polynomial...

arxiv.org
57
195
142
1,848
1,009,530
Ryan O'Donnell retweeted
Anthony Leverrier@letonyoSep 24
oh that's interesting! The authors share the draft generated by Astra, as a companion to their arxiv submission. arxiv.org/abs/2609.28028
7
6
2
146
18,656
STOC 2027 Call for Papers is out: acm-stoc.org/stoc2027/stoc20… Note quite a lot of changes from previous STOC CfPs.
4
19
4
118
35,957
Ryan O'Donnell retweeted
Ola Svensson
@AlgoSvenssonSep 15
An amazing result in online algorithms. I worked on this for over a decade and it is fantastic to see a solution that looks very clean! Also great to see an expert behind the wheels. Congratulations @sahilsingla81 arxiv.org/abs/2609.14555

The Matroid Secretary Conjecture is True

We resolve the matroid secretary conjecture, giving an online algorithm that accepts each element of the offline optimum with probability at least $1/4$. The algorithm only needs the number of...

arxiv.org
2
31
4
204
16,832
Outstanding progress towards the Unique Games Conjecture posted by Yumou Fei, Dor Minzer, and Shuo Wang: eccc.weizmann.ac.il/report/2… 👀
4
35
3
213
46,713
h/t to Noah Singer @singerng_ for pointing me to the paper
1
3
4,440
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 youtube.com/@ComplexityTheor… which will later also feature student videos. We did Williams (/Cook-Mertz/Shalunov) TIME(t) in SPACE(~√t) today.

Complexity Theory At Carnegie Mellon

youtube.com
7
99
10
659
73,247
I gave a talk at Carnegie Mellon about the recent proof (by OpenAI) of the existence of a non-sofic group: youtu.be/uOQvzLjJK6c

A non-sofic group

A talk at the Carnegie Mellon ACO seminar in the math department ab...

youtube.com
3
23
4
165
48,408
Ryan O'Donnell retweeted
Chris Peikert@ChrisPeikertAug 10
Oh my goodness… eprint.iacr.org/2026/1630
21
101
44
474
279,413
Ryan O'Donnell retweeted
Ryan O'Donnell@BooleanAnalysisMay 18
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/focs20… dblp.org/db/conf/focs/focs20… dblp.org/db/conf/focs/focs96…

FOCS Test of Time Award – Call for Nominations 2026 - IEEE Computer Society Technical Committee on...

FOCS 2026 Test of Time Awards Call for Nominations The 2026 FOCS Test of Time Awards, awarded annually, recognize papers published in the Proceedings of the Annual IEEE Symposium on Foundations of...

tc.computer.org
4
20
3,416
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/focs20… dblp.org/db/conf/focs/focs20… dblp.org/db/conf/focs/focs96…

FOCS Test of Time Award – Call for Nominations 2026 - IEEE Computer Society Technical Committee on...

FOCS 2026 Test of Time Awards Call for Nominations The 2026 FOCS Test of Time Awards, awarded annually, recognize papers published in the Proceedings of the Annual IEEE Symposium on Foundations of...

tc.computer.org
4
20
3,416
Ryan O'Donnell retweeted
Noah Singer@singerng_19 Aug 2025
New w/ Meghal Gupta, William He, @BooleanAnalysis arxiv.org/abs/2508.09422 We give a quadratically faster classical algo for noisy planted kXOR (k > large const), dispelling (for now) claimed quartic speedup for quantum algos. 🧵 (1/10)

A Classical Quadratic Speedup for Planted $k$XOR

A recent work of Schmidhuber et al (QIP, SODA, & Phys. Rev. X 2025) exhibited a quantum algorithm for the noisy planted $k$XOR problem running quartically faster than all known classical...

arxiv.org
1
7
1
32
3,944
In case you're in Cambridge, MA on Tue. Dec. 10, I'll give a talk at 4pm (MIT 32-G449) about coboundary expansion in high-dimensional expanders. It's kind of about group theory, though. toc.csail.mit.edu/node/1671 Besides coauthor @singerng_, here's the cast of characters:
1
2
24
3,866
Student I know wants to apply for a PhD program doing quantum computing. But she also wants to be in the *math* department. My brain couldn't do the lookup "QC person but in Math dept." Any suggestions for universities having such a person? Diverse suggestions (by DM) welcome!🙏
26
1
1
49
13,604
I just posted the 100th and final video in my YouTube course, "Quantum Computer Programming in 100 Easy Lessons". If you're interested in learning quantum computing, and you have some 100 consecutive days with a half-hour free, maybe check it out :-) youtube.com/playlist?list=PL…
1
24
1
155
12,925
In case you're in the Boston area, I'll talk about "Quartic quantum speedups for planted inference" tomorrow (Sep. 13) at Harvard at 4pm. This is at the Freedman CSMA Seminar. cmsa.fas.harvard.edu/event/f…
1
11
2,229
Load more