Noah Stephens-Davidowitz
@noahsd.bsky.social
Nerd, computer scientist (http://noahsd.com), Cornell CS prof. I spend a lot of time thinking about lattices and sometimes other things.
Reposted by Noah Stephens-Davidowitz
I wrote a short expository note about a beautiful result of Carmosino, Gao, Impagliazzo, Mihajlin,
Paturi, and Schneider for certifying NO instances of 3-SUM in roughly n^{3/2} time, beating the fastest known, roughly n^2-time deterministic algorithm: home.cs.colorado.edu/~hbennett/no.... 1/
Paturi, and Schneider for certifying NO instances of 3-SUM in roughly n^{3/2} time, beating the fastest known, roughly n^2-time deterministic algorithm: home.cs.colorado.edu/~hbennett/no.... 1/
home.cs.colorado.edu
January 23, 2026 at 4:36 PM
I wrote a short expository note about a beautiful result of Carmosino, Gao, Impagliazzo, Mihajlin,
Paturi, and Schneider for certifying NO instances of 3-SUM in roughly n^{3/2} time, beating the fastest known, roughly n^2-time deterministic algorithm: home.cs.colorado.edu/~hbennett/no.... 1/
Paturi, and Schneider for certifying NO instances of 3-SUM in roughly n^{3/2} time, beating the fastest known, roughly n^2-time deterministic algorithm: home.cs.colorado.edu/~hbennett/no.... 1/
I wrote up a little blog post proposing a slightly different way to write asymptotic notation. www.solipsistslog.com/a-simple-and...
In short, I think asymptotic notation should usually be written with an INequality. E.g., f(n) <= O(n^2), f(n) < o(log n), f(n) > 2^{-o(n)}, f(n) >= n^{-O(1)}, etc.
In short, I think asymptotic notation should usually be written with an INequality. E.g., f(n) <= O(n^2), f(n) < o(log n), f(n) > 2^{-o(n)}, f(n) >= n^{-O(1)}, etc.
A simple and modest proposal for improving asymptotic notation | Solipsist's Log
www.solipsistslog.com
January 7, 2026 at 6:32 PM
I wrote up a little blog post proposing a slightly different way to write asymptotic notation. www.solipsistslog.com/a-simple-and...
In short, I think asymptotic notation should usually be written with an INequality. E.g., f(n) <= O(n^2), f(n) < o(log n), f(n) > 2^{-o(n)}, f(n) >= n^{-O(1)}, etc.
In short, I think asymptotic notation should usually be written with an INequality. E.g., f(n) <= O(n^2), f(n) < o(log n), f(n) > 2^{-o(n)}, f(n) >= n^{-O(1)}, etc.
Reposted by Noah Stephens-Davidowitz
To kick off 2026, here's a quick thread on a few mountain ascents from 2025, starting at home in Boulder, Colorado with Mount Sanitas (6,798') at night. 1/4
January 1, 2026 at 8:15 PM
To kick off 2026, here's a quick thread on a few mountain ascents from 2025, starting at home in Boulder, Colorado with Mount Sanitas (6,798') at night. 1/4
New paper with Surendra Ghentiyala (my wonderful PhD student) and Zeyong Li (a PhD student at NUS) eccc.weizmann.ac.il/report/2025/... .
I'm super excited about this paper!
I'm super excited about this paper!
ECCC - TR25-210
eccc.weizmann.ac.il
December 9, 2025 at 12:41 AM
New paper with Surendra Ghentiyala (my wonderful PhD student) and Zeyong Li (a PhD student at NUS) eccc.weizmann.ac.il/report/2025/... .
I'm super excited about this paper!
I'm super excited about this paper!
Reposted by Noah Stephens-Davidowitz
Reposted by Noah Stephens-Davidowitz
Sarah Huckabee Sanders was once politely asked to leave a restaurant and it generated 100x as much handwringing from the media as this will
Heavily armed paramilitary forces stormed a local San Diego restaurant today, deployed stun grenades against a crowd of onlookers, and kidnapped a handful of kitchen workers.
May 31, 2025 at 7:45 PM
Sarah Huckabee Sanders was once politely asked to leave a restaurant and it generated 100x as much handwringing from the media as this will
Reposted by Noah Stephens-Davidowitz
Kimbrel's receipt of this honor is well-deserved! To celebrate, I'll discuss the matrix multiplication verification problem and his improvement with R.K. Sinha [KS93] to Freivalds' algorithm [Fre79].
More improvements are ongoing work, joint with @huckbennett.bsky.social and @noahsd.bsky.social!
More improvements are ongoing work, joint with @huckbennett.bsky.social and @noahsd.bsky.social!
Tracy Kimbrel, former National Science Foundation program director extraordinaire, will receive the 2025 ACM SIGACT Distinguished Service Award. He spearheaded programs such as TRIPODS (foundations of data science) and AitF (Algorithms in the Field).
1/2
1/2
June 1, 2025 at 12:17 PM
Kimbrel's receipt of this honor is well-deserved! To celebrate, I'll discuss the matrix multiplication verification problem and his improvement with R.K. Sinha [KS93] to Freivalds' algorithm [Fre79].
More improvements are ongoing work, joint with @huckbennett.bsky.social and @noahsd.bsky.social!
More improvements are ongoing work, joint with @huckbennett.bsky.social and @noahsd.bsky.social!
I don't do this, but I should!
Normalise writing a nice quick note to scholars literally every time you read and like their work. Our world is small and getting smaller. We need encouragement.
May 24, 2025 at 6:07 PM
I don't do this, but I should!
Reposted by Noah Stephens-Davidowitz
The recording of this week's talk, by Palak Jain (@thepalakjain.bsky.social), is now available online as well along with the slides:
"Enforcing Demographic Coherence: A Harms-Aware Framework for Reasoning about Private Data Release"
www.tcsplus.org/welcome/past...
"Enforcing Demographic Coherence: A Harms-Aware Framework for Reasoning about Private Data Release"
www.tcsplus.org/welcome/past...
TCS+ - 2024-2025
2025/05/07: Palak Jain, "Enforcing Demographic Coherence: A Harms-Aware Framework for Reasoning about Private Data Release"
Palak Jain (Boston University)
www.tcsplus.org
May 8, 2025 at 11:02 AM
The recording of this week's talk, by Palak Jain (@thepalakjain.bsky.social), is now available online as well along with the slides:
"Enforcing Demographic Coherence: A Harms-Aware Framework for Reasoning about Private Data Release"
www.tcsplus.org/welcome/past...
"Enforcing Demographic Coherence: A Harms-Aware Framework for Reasoning about Private Data Release"
www.tcsplus.org/welcome/past...
Reposted by Noah Stephens-Davidowitz
I had to upload the clip here because it's frankly insane. Possibly the most insane trump clip yet. His brain is pudding
April 30, 2025 at 12:54 AM
I had to upload the clip here because it's frankly insane. Possibly the most insane trump clip yet. His brain is pudding
Reposted by Noah Stephens-Davidowitz
I also find it interesting that, when kids are learning about primary colours in school, it's presented as some fundamental truth about the wider universe and not merely a quirk about how our eyes work.
April 19, 2025 at 10:24 PM
I also find it interesting that, when kids are learning about primary colours in school, it's presented as some fundamental truth about the wider universe and not merely a quirk about how our eyes work.
An exploration of different quantifiers via Beyonce's single ladies
a black and white photo of three women dancing in swimsuits .
ALT: a black and white photo of three women dancing in swimsuits .
media.tenor.com
April 18, 2025 at 12:13 AM
An exploration of different quantifiers via Beyonce's single ladies
Reposted by Noah Stephens-Davidowitz
Alphanumeric citations [ABC00] strike the right balance between compactness & communication.
Plain numeric citations [1] are compact, but convey no information.
Author-year citations (Aaronson, Barrington, & Coppersmith, 2000) are too verbose, even if abbreviated (Aaronson et al. 2000).
Plain numeric citations [1] are compact, but convey no information.
Author-year citations (Aaronson, Barrington, & Coppersmith, 2000) are too verbose, even if abbreviated (Aaronson et al. 2000).
March 3, 2025 at 6:00 AM
Alphanumeric citations [ABC00] strike the right balance between compactness & communication.
Plain numeric citations [1] are compact, but convey no information.
Author-year citations (Aaronson, Barrington, & Coppersmith, 2000) are too verbose, even if abbreviated (Aaronson et al. 2000).
Plain numeric citations [1] are compact, but convey no information.
Author-year citations (Aaronson, Barrington, & Coppersmith, 2000) are too verbose, even if abbreviated (Aaronson et al. 2000).
Reposted by Noah Stephens-Davidowitz
New work on faster algorithms for the code equivalence problem: eprint.iacr.org/2025/187! This came out of Jean-François Biasse's REU, and three great undergraduates (Drisana Bhatia, Medha Durisheti, and Lucas LaBuff) are among the coauthors.
Asymptotic improvements to provable algorithms for the code equivalence problem
We present several new provable algorithms for two variants of the code equivalence problem on linear error-correcting codes, the Linear Code Equivalence Problem (LCE) and the Permutation Code Equival...
eprint.iacr.org
February 10, 2025 at 7:04 AM
New work on faster algorithms for the code equivalence problem: eprint.iacr.org/2025/187! This came out of Jean-François Biasse's REU, and three great undergraduates (Drisana Bhatia, Medha Durisheti, and Lucas LaBuff) are among the coauthors.
Reposted by Noah Stephens-Davidowitz
A Primer on Indirect Cost Rates
a cartoon says hey everybody an old man 's talking while bart simpson looks on
ALT: a cartoon says hey everybody an old man 's talking while bart simpson looks on
media.tenor.com
February 8, 2025 at 12:51 AM
A Primer on Indirect Cost Rates