svat

Joined 17 years ago

Karma
9,082
Submissions
1,433
Member since
Mar 16
https://shreevatsa.net/
View on Hacker News

Recent submissions

Comment · 2 days ago
Yes has been down for about a week now (since Oct 23). Maybe the server (http://www-cs-faculty.stanford.edu/) was taken down because of the PHP vulnerability? Let's hope it comes back up soon. If there's a specific file or page you were looking for let me know; maybe I have a saved copy :)
Comment · 2 days ago
Both "search" and "everything else" are primarily advertising revenue[1], and advertising spend is always heavier in Q4 because of (Black Friday and) Christmas.

[1]: As the page says,

- "Search" means "ads on Google Search and on other Google properties such as Gmail, Maps and Google Play"

- "Everything else" means "YouTube ads, subscriptions and devices, Google Network and Other Bets".

Comment · 4 days ago
Incidentally, Ryan Williams says (https://x.com/rrwilliams/status/2114891838377320784):

> In fact, one of the first things I wanted OpenAI to check is that no existing cryptosystems are compromised by the result. Apparently they are safe...

so if you trust his trust of OpenAI, then this has no (immediately obvious) bearing on cryptosystems for now.

Comment · 4 days ago
While this has no immediate bearing on P-vs-NP, it is interesting to note:

- Early CS researchers like Donald Knuth entered CS in the days when regularly someone would come up with a surprising faster algorithm for some problem, and their intuitions were that most problems had faster algorithms than you'd expect.

- Later generations of CS researchers, as all the easy algorithms were discovered, and post Karp's definition of NP-completeness (and the Garey & Johnson book, say), began to specialize in proving hardness, and complexity theory with a “zoo” of complexity classes became more about separation and lower bounds, e.g. I've seen algorithms like Arora's PTAS for Euclidean TSP being described as a “failed attempt to prove a lower bound”. So an entire generation of researchers' intuition was mostly in the direction of an elegant universe with neat separation results (even if we couldn't get them).

- So e.g. surveys of computer scientists showed most of them believing that P≠NP, and someone like Knuth has always seemed a bit of an outlier for saying that maybe P=NP: his argument was simply that there are so many possible polynomial-time algorithms that we haven't explored, and maybe one of them with a large exponent could solve NP-complete problems. (In response to arguments that many researchers have failed to find any such algorithms, he would say that many researchers have failed to prove that P≠NP.) E.g. in 2017 when Scott Aaronson wrote his survey (https://www.scottaaronson.com/papers/pnp.pdf = https://www.scottaaronson.com/papers/pnp-kindle.pdf) he wrote:

> Admittedly, it can be hard to tell whether declarations that P = NP are meant seriously, or are merely attempts to be contrarian. However, we can surely agree with Knuth and Lipton that we’re far from understanding the limits of efficient computation, and that there are further surprises in store.

- What we've seen in this month is surprising unexpected algorithms, like o(n log n) algorithms for FFT and integer multiplication, and now this sub–exponential-time algorithm for 3-SAT. (Yes the ETH has had less support than P≠NP but I still gather it's unexpected.)

So (though I don't expect intuitions on P≠NP to change, and probably that's still the right intuition… but I'm just an interested amateur), maybe there will be a bit of a swing of the pendulum back to the idea that maybe clever algorithms exist that we just haven't thought of.

Comment · 4 days ago
I should add a clarification about the phrase “understanding what is in it” in the previous comment, which I realized is ambiguous: obviously, if you care to distinguish what is present vs absent in a paper, you need to read it. But if you care about understanding any new mathematical content it may have (as applies to this case, as I've been saying in this entire thread — if you, like Prof. Harvey care about a potential o(n log n) algorithm, whether or not such an algorithm is contained in OpenAI's paper per se), then it is neither necessary nor (given how it's written) a good idea.

As I said in the linked comment, it does not matter whether the idea came from OpenAI's paper, or was hallucinated by Fable, or was arrived at by the reader while reading a potential nonsensical explanation from Fable: the main message is that the “o(n log n) bound is plausible” and it is valuable to have it come from a human expert.

Comment · 6 days ago
Comment · 6 days ago
Where is he talking about it as if he did? Don't the parts you quoted make it clear he has not?

As I said in the comment above, reading a paper has never been a good way of understanding what is in it; usually you either have someone give a talk or get it explained to you. Besides, as in another thread above (https://news.ycombinator.com/item?id=50195392), what matters here is not what the paper says, but whether an o(n log n) algorithm exists. Harvey's write-up is about some (new) intuition around why we should expect one (i.e. why we should expect something like the paper's proposed algorithm to be correct).

To be specific: is your problem that, having been provoked by the announcement into thinking more carefully about the problem, he has shared whatever understanding he has arrived at, without literally reading every word of the (poorly written) paper? Why is that a problem, according to you?

Comment · 7 days ago
I looked into it, and it seems there are two issues:

- Only a (growing) minority (maybe 15%?) of apps on F-Droid (the "reproducible builds" ones?) are signed with the developer's own keys (rather than being signed by F-Droid), so to avoid the user having to do the 24-hour cooldown, the developer of the app would need to have done developer verification and signed the app with their own keys,

- F-Droid is in principle opposed to developer verification so the F-Droid client itself would probably not count as by a verified developer.

So in principle a user could avoid the 24-hour cooldown by installing the F-Droid client using adb, then installing from F-Droid only the apps signed by developers who have gone through the developer verification flow, but in practice I imagine most of us (as users) will be doing the "Advanced" flow, i.e. the one-time 24-hour cooldown.

Comment · 7 days ago
The paper is not written in a very human-readable way, so he's trying to get at the ideas via alternative means instead. What do you see as the problem with it (let alone "crisis")?

For one thing, this is a model that works; see for example Terry Tao's usage of ChatGPT (https://chatgpt.com/share/6a5fdc7a-d6f8-83e8-bbea-8deb42cfed...) to understand the counterexample to the Jacobian conjecture (though in that case there was no paper to read), and then writing it up (https://terrytao.wordpress.com/2026/07/21/a-digestion-of-the...). This seems exactly parallel here?

For another thing, mathematicians have always followed a practice of not reading papers, or at least not reading them very closely. Writing is a poor medium for the transmission of ideas (Thurston has written about this in many places), and see also https://x.com/littmath/status/2107670379858895001:

> I once had a conversation with Akshay Venkatesh where he was explaining some result to me and I commented “wow, you read that [difficult] paper?” And he replied “well, I imagined I read it.” Made a big impression on me.

and https://x.com/littmath/status/2107827516367110211:

> A lot of people—me included—do not enjoy reading LLM outputs. There’s an alternative!

> Personally I have always been very bad at reading mathematics. But you don’t have to read it by reading it, if that makes sense. Rather, you think in its general vicinity.

Comment · 8 days ago
That's fair; there is some slight evidence in the linked comments of pressure from those governments, but you're right, Google's own comments show it agreeing with the principle. E.g. they say that identifying and banning malicious apps isn't very effective if the developers can make slight changes and distribute modified apps immediately. So the basic idea of anonymous apps having wide distribution is what is being targeted.
Comment · 8 days ago
Comment · 8 days ago
Come on. Prof David Harvey is the leading expert on this exact topic (integer multiplication algorithms), and here he has spent a lot of effort and time to digest the main new idea(s), and write 30+ pages explaining exactly what he's understood and why he believes the result is plausible. About the main “gadget”, he writes “I have worked through all the steps pretty carefully, and I think it checks out.” All this is useful information, and is the best we have so far from a reliable human source. I think it deserves more than a flippant response to the first line.
Comment · 9 days ago
- The author is already the world's best expert on this topic.

- You're right that it's possible Fable came up with a different o(n log n) algorithm that is not in OpenAI's paper, but (apart from being unlikely) it doesn't matter, as he talks of the belief that “the main result is possibly correct”, not necessarily that OpenAI's paper is: whether the argument comes from the paper or from Fable, the question of interest is whether multiplication is really possible in o(n log n) time. The point is that there's a genuine idea here, somewhere between OpenAI's paper and Fable's explanation of it and the author's understanding of it.

- This is in fact how mathematicians have evaluated papers for decades: is there any way this result could be true? Is there an actual idea here that could help? Do I understand enough of the argument to be convinced it's likely true, modulo some details that need to be filled in? The last step (actually filling in the details) happens when teaching it to someone else or writing it again in one's own words.

Comment · 9 days ago
The very next lines say:

> At first I did not understand Fable’s explanations. But I asked questions, and then asked more questions, and drilled down towards the core of the problem. Gradually I started to understand parts of the argument. I have seen enough now to arrive at the tentative belief that the main result is possibly correct […] In the sections below I will try to explain what I have learned so far, and why I lean towards thinking it might be correct.

So the whole paper is about things the author does understand. (BTW the author David Harvey was behind the big advances in integer multiplication, in 2014 and 2019/2021.)

Comment · 1 month ago
Every community approaches problems with the tools at its disposal. Doing mathematics is about thinking, so mathematicians approach problems (at least in public) with more thinking and less emotion (than some fields where emotion is much more important). While you and I may appreciate this approach (and even be inspired by it), it remains to be seen whether it ultimately makes the outcomes any better.

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton