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.
Right, my comment was not about its usefulness. I was merely pointing out that those results do not necessarily imply any kind of actual understanding.
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.
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.
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.
I find it slightly less weird because I see potential for indirect attacks on the not-quite-so-ECC parts of actual implementations. Wherever a network client can ask many times for each of the different, but somehow not entirely uncorrelated curves, it might be able to expose previously not deemed critical side channels. Following in the general direction of the discoveries that so far resulted in IV and padding determinism/randomness being considered as important as the "actual crypto" itself. In that case the structures that would need to somehow interact would not be ECC and LCG, but merely LCG and key derivation..
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
Note that incorrect code can still cause
1. incorrect outputs, or
2. arbitrary performance degredations
safe rust doesn't have to work magic. All it must do is prevent UB.
reply