svat
Joined 17 years ago
Joined 17 years ago
[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".
> 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.
- 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.
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.
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?
- 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.
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.
- be a registered developer, and target all Android users (Google Play Store, F-Droid, distributing .apk files, etc), or
- remain anonymous, and target only a subset of Android users (all "power users" who do the one-time 24-hour cooldown, or a small number of users if you use the student/hobbyist path, and of course anyone can install their own apps on their own device with adb).
This is definitely an unfortunate step backwards from Android's prior openness, but is still more open than iOS (my comparison from a previous discussion: https://news.ycombinator.com/item?id=47939361), and is basically Google being forced by the governments of certain countries (Brazil, Indonesia, Singapore, Thailand) where malicious-app phone scams have led to a lot of people losing their savings (https://news.ycombinator.com/item?id=47152069 https://news.ycombinator.com/item?id=45909348).
- 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.
> 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.)