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?

it's worth clarifying that Fourier-based integer multiplication as a general class of algorithms are not galactic. For example, there are techniques that are competitive on some computing platforms for as few as 2048 bits, which occurs during RSA encryption

https://eprint.iacr.org/2022/439

this doesn't use the literal n \log n algorithm, which may be galactic. but it uses fundamentally similar techniques.

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

there have been explicit attempts at this in the past. Nicholas Bourbaki was the pseudonym of a group of French mathematicians who had this goal mid 20th century. You can see e.g.

https://en.wikipedia.org/wiki/%C3%89l%C3%A9ments_de_math%C3%...

It has many benefits, and many people appreciate the books. It also has many downsides. For example, they started publishing in 1939. As part of this, they needed to work through the basis that most other mathematical objects are defined in terms of (they used sets).

Unfortunately for them, contemporaneously with their work, other mathematicians were beginning to define mathematical objects (categories) that can be an alternative basis for mathematics, which many modern expositions prefer to sets. So, their approach either

1. needed a massive "refactoring", or

2. would be hopelessly dated.

They ended up going with the approach that is now dated. It may sound peculiar that mathematics can be "dated". But it very much can. The mathematics community can go through many different styles for how to explain/collect mathematical understanding. Different styles can have different benefits, and be easier/harder for different subfields. A simplified/unified perspective will necessarily privilege certain perspectives.

It is analogous to how you might want there to be a simplified/unified (set of) libraries for programming. Perhaps that everyone uses. This sounds nice, and many programming languages do this with their standard libraries. But these always make concessions! I'll speak about Rust's, as I'm most familiar

1. fallible allocation or infallible allocation?

2. C-style strings or (ptr, len) strings?

3. Should interfaces take as input &mut [T] references, or should they take as input T in an "owned" way (this would make compatibility with io_uring easier)

for each, it is not that one answer is right. Both can be argued for. You have to choose one. The one choice may not be satisfactory for every practitioner though.

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

that's misunderstanding what lean does. It proves many statements of the form A implies C (I'll write this as A => C). If you chain many of these together, say A => B1 => B2 => ... => B500_000 => C, what you do is

1. examine A, and

2. examine C, and

3. rely on the Lean kernel to ensure that all of the interior transitions are correct.

Modulo a soundness bug in the lean kernel (which do occur), the entire proof is then correct, even if you only need to inspect the small fragments A and C to understand if this correct proof is interesting. But the semantics of the statements B1 ... B500_000 are irrelevant to the correctness of the final implication A => C (again, modulo soundness bugs in the lean kernel).

while yarvin does not explicitly adopt the label of facist (and I might personally argue that it doesn't match him), he explicitly espouses for the fall of American democracy, and a return to a monarchist system.

I would imagine many people would find support of a modern-day, somewhat influential (he has several followers in Trump's administration, as well as among several right-wing billionaires) monarchist to be notable/distasteful.

the apple lawsiut about hw theft at openai is ongoing lol

see the Grothendiek prime

https://en.wikipedia.org/wiki/57_(number)

those numbers are "adjusted" though. so they are not profitable by the standard definition.

helicoptors are a much more dangerous way to travel though? this is already true in the best of times/when you aren't anticipating a possible attack on the passengers.

there's a funny paper on this theme, titles "Could a Neuroscientist Understand a Microprocessor"

https://pmc.ncbi.nlm.nih.gov/articles/PMC5230747/

roughly, it reviews common techniques in neuroscience, and comes to the conclusion that they would not be able to understand even simple computing platforms that we have perfect information for (and can perfectly stimulate any internal connection, can perfectly read out the values on any internal connection, etc).

tanks have very much run over people to kill them. a wheel can very much be used as a weapon.

isn't blitzscaling essentially the same thing, except for when American companies do it (not always within their own country, e.g. spotify, netflix, or amazon)

the way LLMs write math is not beautiful. it is exactly analogous to the software that LLMs develop is not beautiful. it may achieve impressive end products, but if you like understanding the methods/architecture, looking under the hood is often a field of horrors.

I won't take a side in things, but OpenAI stated the model they used here started training August 28th. Note that "training" here might mean "post-training with RLHF an Astra base model" or something. but training had only started a little over a week earlier.

worth mentioning there's some indication the 240k peak was massively inflated by bot accounts. but by all means there are many fewer bot accounts this year, and it's still ~150k concurrents frequently. so it's still doing very well, but the numbers are a little different.

I guess I don't understand the issue you're raising. If you want to formalize a non-constructive proof, it remains non-constructive, even if you have a computer check the proof vs a human.

As a trivial example, in lean you can work with probability theory/measure theory. This has oodles of non-constructive parts, but we can ignore that for now. As part of this, you can use the probabilistic method. For example, if you want to prove that codes with optimal parameters exist, for many noise models it is known that sampling a code randomly from an appropriate (and often naive) distribution will yield a code with optimal parameters.

You should be able to prove this in lean (or any other theorem prover). But you cannot construct these codes. While you can sample a code randomly, verifying a code has good parameters is typically NP-hard (e.g. it is an instance of the minimum distance problem). So, you cannot (efficiently) "construct" a good code in lean4, despite being able to prove one exists.

This seems analogous to me that you could validate that a non-constructive proof is correct in lean4. Sure, it would be nice if the proof was constructive. But it isn't, and encoding it into a computer shouldn't give you that (non-trivial) property for free.

if Stadlmann used a previous OpenAI product, and Astra was trained off of her chat, and had a comparable approach, then it might be comparable.

they're using a new model trained since the prompts happened. They are not denying the other group's solution may have been in their model weights, despite it being unreleased.