mswphd

practically, a poly-time reduction can increase teh size of hte problem instance. So maybe you transform a 3-color instance (graph on n vertices) into a n^2 sized SAT instance. You can then solve this in time 2^{n^2 / sqrt{log{n^2}}}, but this is not sub-exponential.

complex searches are quite valuable in mathematics. For example, Maryna Viazovska's fields medal was for finding the right gadget (roughly, a complex search) to prove optimality results in sphere packings.

yes, but even the dramatic underestimate shows how useless it is. I also imagine that current estimates could be significantly optimized if there was some usecase for them. the 1k-10k multiplication regime has actual usecases, so there has been some optimized implementations of theoretical integer multiplication algorithms in this regime.

it doesn't. it might if you're multiplying numbers in the thousands of digits (but even that is almost assuredly too low). for essentially everyone this is purely a theoretical result.

not at all. even the previous O(n \log n) multiplier is almost never used in practice. In general fourier-based multipliers only start being useful at a minimum when you are multiplying 1000-digit numbers, but even that threshold is low/contentious. they have a definite advantage for ~10,000-digit numbers. this likely has larger overhead, so is only plausibly useful for even larger numbers. you do not often have to multiply these extremely large numbers.

you (mostly) can't. In computing, "random" is a property of a process to generate a number, not a property of a number itself. You cannot directly analyze a number to determine it has been randomly generated.

There are some caveats here. There are some intrinsic properties of numbers that random numbers satisfy with high probability, e.g. having high kolmogorov complexity. But these are generally very difficult to compute, and I would personally guess you could concoct (probably artificial) scenarios where

1. picking parameters randomly yields a secure construction, but

2. there exists a parameter set with high kolmogorov complexity that is insecure.

e.g. "high kolmogorov complexity", while being a property of random numbers, is generally not viewed as nearly as useful as being randomly generated (which is exhibited by saying generator + seed = the particular number, like in this article).

unless your guess is that the hypothetical ECC weakness is somehow correlated with the LCG structure, the draws from the LCG are as good as random.

It is possible such a correlation could occur. but it would be much weirder than this being the result of a random search, which would already be very weird.

why though? in particular if the NSA wanted to hide their nefarious intent here, why wouldn't they use something stronger than an LCG so the question for how they're generated remained open forever?

I've heard that certain inference providers may have different quality of caching implementations, so even if the listed numbers are as you say, the practical cache hit % you get might be significantly different/incur significantly different costs.

communicating results clearly is just as important for specialists/experts. A reaction by many mathematicians to the OpenAI dump (and many LLM breakthroughs) is simultaneously

1. if this is true, it is interesting, and

2. the exposition of this is a huge pile of slop.

This requires mathematicians to have to clean up the slop for it to be useful. It has happened for most LLM-generated proofs in the last few months. Anthropic explicitly payed two top complexity theorists to do it for the 3SUM and APSP breakthrough.

They didn't do this because those complexity theorists are advocating for a tyranny of the illiterate lmao

for say FFT/integer multiplication or 3SUM, we have natural algorithms that have existed a long time with a given complexity (O(n \log n) and O(n^2), respectively). Given how long these natural algorithms have been the best algorithms we have, it is natural to conjecture they are optimal. Showing an O(n(\log n)^{.99999}) algorithm exists shows that these optimality conjectures are false.

Now, there are some critiques you can have of this. Namely, it is possible that these novel algorithms have significant trade-offs that make them almost never worthwhile in practice. "Fast" matrix multiplication algorithms are typically of this form. So perhaps this all points towards a deficiency in big O notation, which can be deceptive. But, for people who care about optimizing asymptotic complexity, it is still interesting.

to depress you even more, it is consistent with everything that we know that P != NP and that cryptography does not exist. So there is a worst of both worlds, and we cannot rule it out.

worth mentioning that "NP" is not "non-polynomial" but "non-deterministic polynomial (time)". If NP was non-polynomial time then NP != P would be trivial (and in fact, P != EXP is known by the time hierarchy theorem).

Non-deterministic can be explained in several ways. One is in terms of a hypothetical "nondeterministic Turing machine" with certain non-physically realizable properties. The easier way is that a NP problem gets as input not only the problem instance x, but a "witness" w, that may depend on the problem instance. This witness generally makes the problem of deciding the problem instance straightforward (e.g. for SAT, x is the SAT instance, and w is a description of how to set the variables so that it is true).