@BooleanAnalysis

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

 Pittsburgh, PA
cs.cmu.edu/~odonnell/
Joined October 2011
  • Tweets742
  • Following0
  • Followers7.7K
234Media
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,505
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,576
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
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
205
16,832
Ryan O'Donnell retweeted
Chris Peikert@ChrisPeikertAug 10
Oh my goodness… eprint.iacr.org/2026/1630
21
101
44
474
279,414
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
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
Three world-leading mathematicians, Irit Dinur, Elon Lindenstrauss, and Aaron Naber, have been appointed to the Institute Faculty, bringing unique expertise in pure mathematics and computer science. They will begin their IAS appointments this summer. More: ias.edu/news/three-world-lea…
16
3
145
22,460
Ryan O'Donnell retweeted
Barna Saha@B1ar2n3a18 Jun 2024
I am urging the entire TCS community to attend the TCS for All inspiration talk to be given by Luca Trevisan to honor his contributions and to be there for him and his family at this very difficult time. I will be sharing the registration link shortly. Registration will be free.
2
30
1
98
36,081
Ryan O'Donnell retweeted
Tom Gur@TomGur15 Jun 2024
Gil Cohen is teaching a fantastic course about Free Probability (generalising classical probability theory to the non-commutative setting) from the perspective of theoretical computer science. Highly recommended! Lecture recordings are available here: youtube.com/playlist?list=PL…

Free Probability Theory and Ramanujan Graphs - Spring 2024

These are the recorded lectures, given in English, for a course I am currently teaching at Tel Aviv University (in the Spring of 2024). The goal is to introd...

youtube.com
1
26
2
264
20,423
Ryan O'Donnell retweeted
Anupam Gupta@anupamg5 May 2024
Reminder: the #stoc2024 early registration deadline is tomorrow (Monday May 6)! Great set of papers and talks, now including the Turing Award lecture by Avi Wigderson!
Anupam Gupta@anupamg29 Mar 2024
The registration for STOC 2024 is open. acm-stoc.org/stoc2024/regist… In addition to the STOC 2024 paper talks (of course!), featuring keynote talks by @MichalFeldman9, @merettm, and @Tim_Roughgarden. And workshops (see next post, margins too small to write here). #STOC2024
3
23
6,465
Ryan O'Donnell retweeted
Anupam Gupta@anupamg29 Mar 2024
The registration for STOC 2024 is open. acm-stoc.org/stoc2024/regist… In addition to the STOC 2024 paper talks (of course!), featuring keynote talks by @MichalFeldman9, @merettm, and @Tim_Roughgarden. And workshops (see next post, margins too small to write here). #STOC2024
1
10
2
56
28,089
Ryan O'Donnell retweeted
Gil Kalai@GilKalai13 Nov 2023
The polynomial Freiman-Ruzsa conjecture has been solved! gilkalai.wordpress.com/2023/…

Marton’s “Polynomial Freiman-Ruzsa” Conjecture was Settled by Tim Gowers, Ben Green, Freddie...

Gowers, Green, Manners and Tao. They reminded me of the A-team of the 1980s television series: “If you have a problem, if no one else can help, and if you can find them, maybe you can hire…

gilkalai.wordpress.com
3
65
7
292
70,229
Congratulations to Aayush Jain, whose dissertation receives the 2022 ACM Doctoral Dissertation Award! Honorable Mentions go to Alane Suhr @alsuhr , whose PhD was earned at @Cornell , and Conrad Watt @conrad_watt , who earned his PhD at @Cambridge_Uni . bit.ly/2VXooaE
1
13
7
89
29,256
If this holds up, and I'm told the signs look good, then it is the last major step in a long quest to find out how dense a subset of {1,2,...,n} needs to be before it necessarily contains an arithmetic progression of length 3. 1/ arxiv.org/abs/2302.05537

Strong Bounds for 3-Progressions

We show that for some constant $β> 0$, any subset $A$ of integers $\{1,\ldots,N\}$ of size at least $2^{-O((\log N)^β)} \cdot N$ contains a non-trivial three-term arithmetic progression....

arxiv.org
2
26
3
168
50,898
Ryan O'Donnell retweeted
FanPu Zeng
@FanPu_Zeng11 Jan 2023
I curated a list of publicly-accessible courses from CMU, ranging from machine learning to computer systems to CS theory. Videos are high quality (many same as what CMU students get), most HWs also public on website. Great for self-study & review. Link: fanpu.io/cmu-online/
3
96
1
373
60,740
Ryan O'Donnell retweeted
ICPCNews
@ICPCNews10 Nov 2022
Silver Medalist Carnegie Mellon University 9 problems solved #icpcwfdhaka
2
5
2
44
1/3: Sun Aug 28, 11AM ET, Prof. Lenore Blum of Carnegie Mellon University, AAAS Fellow, Noether Lecturer, Presidential PAESMIEM awardee (see her wiki page at en.wikipedia.org/wiki/Lenore… for more info) and myself plan to have a YouTube broadcast @hajiaghayi, and here at Twitter.

Lenore Blum - Wikipedia

en.wikipedia.org
1
3
2
10
The Istanbul Center for Mathematical Sciences (IMBM), Turkey's premier research center for mathematics, has now been shut down by the Bogazici rectorate. We are all in shock but are also resolved to working to having this decision overturned. imbm.org.tr
6
138
19
466
Load more