iiinova — where your digital self keeps evolving

Reposted by Noah Stephens-Davidowitz

Mike Masnick @masnick.com · 11/09/2026

Just did a quick look around and I don't see very many headlines about the President of the US making people pledge allegiance to him personally while telling everyone to commit election fraud and "cheat like hell" to support his party. Seems like it should be a story?

5758181884

Reposted by Noah Stephens-Davidowitz

Huck Bennett @huckbennett.bsky.social · 17/08/2026

Here's a thread about four papers of mine that are being presented at conferences this week. I won't be at any of them due to the start of classes at CU, but my awesome students and collaborators will! (And, no, none of these papers used AI except for typo checking in one case.) 1/

181

Noah Stephens-Davidowitz @noahsd.bsky.social · 02/08/2026

It's difficult for me to separate the message from the messenger here. There's the fact that it was produced by AI. And, there's the fact (that @henryyuen.bsky.social also mentioned) that it's written pretty poorly. I think it will take some time to figure out what actually happened here :-/.

280

Noah Stephens-Davidowitz @noahsd.bsky.social · 02/08/2026

It's crazy. They didn't "only" prove hardness of CVP with a polynomial approximation factor. They also made the first improvement in decades on sphere packing AND on the optimal minimum distance of codes. (And they solved open problems in a bunch of other fields that I know less about.)

170

Noah Stephens-Davidowitz @noahsd.bsky.social · 02/08/2026

I'm glad to hear someone else say this publicly. The writeup is really frustrating.

010

Reposted by Noah Stephens-Davidowitz

Henry Yuen @henryyuen.bsky.social · 01/08/2026

Some initial thoughts, and a complicated mix of feelings. Wow. I mean, Erdos problems are cool (I genuinely mean that), I didn't know about the Jacobian conjecture before it got disproved. But this newest batch from OpenAI hits home in a way the previous announcements did not.

232972

Reposted by Noah Stephens-Davidowitz

Bas Westerbaan @bwesterb.bsky.social · 09/07/2026

Every year we write about the exciting developments in post-quantum signatures. Last year didn't disappoint. But it's too late. As ekr wrote in 2024 "You go to war with the algorithms you have, not the ones you wish you had." ML-DSA will have to do for now. blog.cloudflare.com/ml-dsa-will-...

blog.cloudflare.com

Why we cannot wait for better post-quantum signature algorithms

NIST is advancing nine new post-quantum signature algorithms as potential candidates for future standardization. We take a closer look at all of them, and argue that while they are in the works and sh...

0116

Reposted by Noah Stephens-Davidowitz

Polling USA @usapolling.bsky.social · 11/06/2026

A reminder of how many times Trump has said a deal is right around the corner with Iran

613962

Reposted by Noah Stephens-Davidowitz

Costa Samaras @costasamaras.com · 28/04/2026

Hold on. We the taxpayers are going to pay companies $900 million, which is more than 6x what we spend on wind power R&D, to NOT build wind power at a time when electricity prices are spiking and we need more clean power?

24263052781

Noah Stephens-Davidowitz @noahsd.bsky.social · 02/03/2026

I don't think this is relevant cryptographically. The DEL25 result that they're comparing to is far from the state of the art. (DEL25 were mostly interested in a different parameter regime.) And the claimed running time of this new attack is way higher than the claimed security of Dilithium.

130

Reposted by Noah Stephens-Davidowitz

Michael Kinyon @profkinyon.bsky.social · 27/02/2026

Me, writing a proof of a "the following are equivalent" theorem: "(2) implies (3) is trivial" No, that's not supercilious enough "Only a nincompoop would fail to see that (2) implies (3)" No, that one would never get past the Editor "(2) implies (3) is, of course, trivial" Perfect

1152

Reposted by Noah Stephens-Davidowitz

arXiv @arxiv.bsky.social · 27/02/2026

Today arXiv remembers our colleague Joe Halpern, who was instrumental in founding arXiv's CS section. Joe's passions ranged far & wide and we're lucky that arXiv was one of them. Joe, thank you for giving so much to arXiv - you are missed. blog.arxiv.org/2026/02/27/remembering-joe-halpern

A picture of Joe Halpern smiling in green shirt in front of a blue background.

25414

Reposted by Noah Stephens-Davidowitz

Huck Bennett @huckbennett.bsky.social · 23/01/2026

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/

home.cs.colorado.edu

2213

Noah Stephens-Davidowitz @noahsd.bsky.social · 18/01/2026

I think what I'm proposing just achieves the best of all worlds here? You can write f(n) <= g(n) + O(h(n)) and maintain the flexibility of big-O notation while achieving the clarity of an inequality rather than a "one-way equality."

000

Noah Stephens-Davidowitz @noahsd.bsky.social · 18/01/2026

But, Knuth prefers big-O because it's cumbersome to use << to write, e.g., f(n) = g(n) + O(h(n)). One would have to write f(n) - g(n) << h(n), which would be annoying in more complicated settings if one wants to write something like f(n) = g(n) + h_1(n) = g(n) + O(h_2(n)) or something.

100

Noah Stephens-Davidowitz @noahsd.bsky.social · 18/01/2026

He then says that the notation f(n) << g(n) (or similar) has the huge benefit that it is clear and doesn't yield the weird "one-way equalities" that one gets from f(n) = O(g(n)).

100

Noah Stephens-Davidowitz @noahsd.bsky.social · 18/01/2026

Thanks for the link! It looks like Knuth says that they're best thought of as sets, but we should still write equalities and not set inclusion because that's what people are used to.

110

Noah Stephens-Davidowitz @noahsd.bsky.social · 18/01/2026

Much butter, and also much better :).

000

Noah Stephens-Davidowitz @noahsd.bsky.social · 18/01/2026

I feel like that's technically incorrect, but not in a way that is likely to be misunderstood. So, it's much butter than saying "if m is O(n^2)" to mean "if m >= C n^2", which is both incorrect and likely to be misunderstood.

200

Noah Stephens-Davidowitz @noahsd.bsky.social · 07/01/2026

I know that this is not an original idea. It seems that many authors use this notation already, at least in some contexts. I have not seen anyone advocate for its widespread adoption, so I thought I would.

010

Noah Stephens-Davidowitz @noahsd.bsky.social · 07/01/2026

A more subtle example is something like f(n) = n^2 + O(n). This sometimes means f(n) <= n^2 + O(n), but it often means |f(n) - n^2| <= O(n). Note that using inequalities here again removes this ambiguity.

100

Noah Stephens-Davidowitz @noahsd.bsky.social · 07/01/2026

This sometimes removes ambiguity. E.g., f(n) = poly(n) is ambiguous. This can mean that f(n) is upper bounded by a polynomial in n, that it's lower bounded, or both. I think one should write f(n) <= poly(n), f(n) >= poly(n), and f(n) = poly(n) to distinguish these cases.

110

Noah Stephens-Davidowitz @noahsd.bsky.social · 07/01/2026

For more complicated expressions like f(n) <= 1/(1-O(1/x)) or whatever, the inequality is useful to help the reader know whether an upper bound or a lower bound is implied by the notation.

120

Noah Stephens-Davidowitz @noahsd.bsky.social · 07/01/2026

I think this notation makes it much clearer what we mean. It also solves the annoying problem that something like "f(n) = O(n^2)" is an abuse of the equals sign, which pedants (like me) often complain about.

100

Noah Stephens-Davidowitz @noahsd.bsky.social · 07/01/2026

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.

solipsistslog.com

A simple and modest proposal for improving asymptotic notation | Solipsist's Log

5165

Reposted by Noah Stephens-Davidowitz

Huck Bennett @huckbennett.bsky.social · 01/01/2026

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

2101

Noah Stephens-Davidowitz @noahsd.bsky.social · 12/12/2025

This isn't exactly what you want, but the composition series seems closely related.

100

Noah Stephens-Davidowitz @noahsd.bsky.social · 09/12/2025

Let me finish with a fun technical tool: We show an AM protocol that *upper* bounds the image size of a circuit C. This is kind of dual to the celebrated Goldwasser-Sipster protocol, which gives an AM protocol that *lower* bounds this (or any NP set). This seems likely to have other applications!

010

Noah Stephens-Davidowitz @noahsd.bsky.social · 09/12/2025

Avoid could be such a problem itself. However, our work doesn't rule out a reduction from a hard decision problem that lies in AM ∩ co-AM---even a well-studied problem like, say, factoring.

100

Noah Stephens-Davidowitz @noahsd.bsky.social · 09/12/2025

A key subtlety here is the distinction between search and decision. As a trippy example, there exist search problems A such that (1) every *decision* problem that reduces to A is efficiently solvable; but (2) A itself is not efficiently solvable. (It's a fun exercise to come up with such a problem.)

100

Noah Stephens-Davidowitz @noahsd.bsky.social · 09/12/2025

For example, this immediately implies that the (co-NP-complete) problem of verifying solutions to Avoid does *not* reduce to Avoid unless PH collapses, which is just trippy! (Lots of things about Avoid are quite trippy!)

100

Noah Stephens-Davidowitz @noahsd.bsky.social · 09/12/2025

We show that this is unlikely. For example, we show that NP-hardness of Avoid would collapse the polynomial hierarchy (to AM). More generally, we show that any decision problem that reduces to Avoid is in AM ∩ co-AM. (This works even for adaptive, randomized reductions.)

110

Noah Stephens-Davidowitz @noahsd.bsky.social · 09/12/2025

Basically, Korten showed that an algorithm would allow us to derandomize *many* randomized constructions. However, this left open the question of whether we simply reduce a well-studied presumed hard problem to it to show that Avoid is hard. Ideally, we'd like to show NP-hardness.

100

Noah Stephens-Davidowitz @noahsd.bsky.social · 09/12/2025

Avoid is not only weird, but also important. E.g., Korten and Jeřábek showed that it is in FP^{NP} if and only if E^{NP} requires 2^{\Omega(n)}-size circuits!! And, Korten showed that an algorithm for Avoid would yield nearly optimal two-source extractors, rigid matrices, hard truth tables, etc.

100

Noah Stephens-Davidowitz @noahsd.bsky.social · 09/12/2025

I find this problem to be endlessly fascinating because of how weird it is. For example, Avoid is clearly hard in some sense, since just *verifying* a solution is coNP-complete. On the other hand, Avoid is clearly easy in some sense, since a random string is a solution with probability 1/2.

100

Noah Stephens-Davidowitz @noahsd.bsky.social · 09/12/2025

The input to Avoid is a circuit C : {0,1}^n -> {0,1}^{n+1}. Since C is expanding, there must be some string (in fact, many strings) y \in {0,1}^{n+1} that are not in the image of C. The goal is to find such a y that is not in the image.

100

Noah Stephens-Davidowitz @noahsd.bsky.social · 09/12/2025

We study the range-avoidance problem (Avoid), which was introduced by Kleinberg, Korten, Mitropolsky, and Papadimitriou in 2021. This problem gained a ton of attention after Korten showed that it has deep connections to derandomization and circuit lower bounds.

110

Noah Stephens-Davidowitz @noahsd.bsky.social · 09/12/2025

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!

eccc.weizmann.ac.il

ECCC - TR25-210

181

Reposted by Noah Stephens-Davidowitz

Kevin M. Kruse @kevinmkruse.bsky.social · 31/05/2025

Sarah Huckabee Sanders was once politely asked to leave a restaurant and it generated 100x as much handwringing from the media as this will

176101363044

Reposted by Noah Stephens-Davidowitz

Adithya Bhaskara @adithyacolorado.bsky.social · 01/06/2025

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!

152

Reposted by Noah Stephens-Davidowitz

TCS+ @tcsplus.bsky.social · 08/05/2025

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...

tcsplus.org

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)

034

Reposted by Noah Stephens-Davidowitz

Rude Law Dog @esghound.com · 30/04/2025

I had to upload the clip here because it's frankly insane. Possibly the most insane trump clip yet. His brain is pudding

2902747778

Reposted by Noah Stephens-Davidowitz

Thomas Steinke @stein.ke · 19/04/2025

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.

1151