Noah Stephens-Davidowitz

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.

224 followers179 following52 posts

Noah Stephens-Davidowitz reposted

Ryan Williams
@rrwilliams.bsky.social

An internal model at OpenAI has produced a claimed refutation of ETH! Russell Impagliazzo, Mohan Paturi, and I have been asked to help organize an open and independent examination of this claim. 1/4

Noah Stephens-Davidowitz
@noahsd.bsky.social

~Six years ago, I proposed this as an open problem. I actually said that it was easy to solve. Then I realized that it was very hard and got stuck on it for 5 years. Then, Aditya and Divesh (but, let's be honest, mostly Aditya) pointed out that if you look at it in the right way, it's easy.

Noah Stephens-Davidowitz
@noahsd.bsky.social

Did anyone think that integer multiplication and the Fourier transform were solvable in n log^{1-\eps}(n) time? That seems insane to me. I think the only reason that this wasn't a widespread conjecture is because it wouldn't have many interesting implications.

Noah Stephens-Davidowitz
@noahsd.bsky.social

Are people finding the new OpenAI papers to be exceptionally hard to read (like the previous batch)? I tried the Quasi-Riemann hypothesis paper (which, admittedly, is quite far from my area of expertise), the lattice covering paper, the integer multiplication paper, and the L = RL = BPL paper.

Noah Stephens-Davidowitz reposted

Mike Masnick
@masnick.com

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?

Aaron Rupar@atrupar.com

Trump: "Please right your right hand. I pledge to the greatest president in the history of the United States. That loves us so much he can't even breath. That I will go out with my family, my friends, I'll do it any way - I don't care if I'm registered or not, I'm going to try to cheat like hell..."

Noah Stephens-Davidowitz reposted

Huck Bennett
@huckbennett.bsky.social

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/

Noah Stephens-Davidowitz reposted

Henry Yuen
@henryyuen.bsky.social

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.

Noah Stephens-Davidowitz reposted

Bas Westerbaan
@bwesterb.bsky.social

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.comWhy we cannot wait for better post-quantum signature algorithmsNIST 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...

Noah Stephens-Davidowitz reposted

Michael Kinyon
@profkinyon.bsky.social

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

View full thread
Noah Stephens-Davidowitz
@noahsd.bsky.social

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.

Noah Stephens-Davidowitz
@noahsd.bsky.social

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.

View full thread
Noah Stephens-Davidowitz
@noahsd.bsky.social

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.

Noah Stephens-Davidowitz
@noahsd.bsky.social

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.

Noah Stephens-Davidowitz reposted

Huck Bennett
@huckbennett.bsky.social

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

View full thread
Noah Stephens-Davidowitz
@noahsd.bsky.social

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!

View full thread
Noah Stephens-Davidowitz
@noahsd.bsky.social

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

Noah Stephens-Davidowitz
@noahsd.bsky.social

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

View full thread
Noah Stephens-Davidowitz
@noahsd.bsky.social

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.

Noah Stephens-Davidowitz
@noahsd.bsky.social

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

View full thread
Noah Stephens-Davidowitz
@noahsd.bsky.social

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.

Noah Stephens-Davidowitz
@noahsd.bsky.social

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.

Noah Stephens-Davidowitz
@noahsd.bsky.social

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.

Noah Stephens-Davidowitz
@noahsd.bsky.social

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.

Noah Stephens-Davidowitz reposted

Adithya Bhaskara
@adithyacolorado.bsky.social

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!

Lance Fortnow@lance.fortnow.com

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

Noah Stephens-Davidowitz reposted

TCS+
@tcsplus.bsky.social

Replying to @tcsplus.bsky.social

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.orgTCS+ - 2024-20252025/05/07: Palak Jain, "Enforcing Demographic Coherence: A Harms-Aware Framework for Reasoning about Private Data Release" Palak Jain (Boston University)

Noah Stephens-Davidowitz reposted

ESG Hound
@esghound.com

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

Aaron Rupar@atrupar.com

TRUMP: He had MS-13 on his knuckles, tattooed! MORAN: That was photoshopped TRUMP: Terry, they're giving you the big break of a lifetime. I picked you. But you're not being very nice. (Can't post the clip here because of @bsky.app's daily video limit but the text tells you what you need to know)

Noah Stephens-Davidowitz reposted

Thomas Steinke
@stein.ke

Replying to @stein.ke

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.