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/

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

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.

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

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.

Much butter, and also much better :).

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.

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.

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.

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.

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.

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.

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.

On brand!

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

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

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!

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.

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

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!)

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

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.

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.

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.

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.

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.

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!

French sign saying (in French) "Crepes and chocolates", left arrow. "Cruel world", right arrow. Harvested from the webs, no idea of attribution.

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

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!