Posted by jonluca 14 hours ago
The Exponential Time Hypothesis Is False [pdf] - https://news.ycombinator.com/item?id=50251661
The reality that Science is a grind and there are thousands of new results every year discovered by regular humans who use a regular human process to cross-check and review.
Treating every result from the AI like a gift from god is getting tiring.
These are really big results from AI, if a human had come up with them we would also be making a really big deal out of them too (maybe not as big of a deal, part of the excitement is that this was from AI and more results of this magnitude may soon follow).
Kakeya / local smoothing (math): The result would resolve the Kakeya conjecture and Stein’s restriction conjecture across all dimensions together. Mathematicians had been making progress one dimension at a time, so this would settle a whole family of central harmonic analysis problems at once.
ETH is false (computer science): ETH has been used as a computational hardness premise in hundreds of papers, so a disproof would undercut a large body of existing complexity results. It would also change what researchers think is achievable for efficient computation.
QCD existence (physics): It would give a rigorous mathematical foundation to the theory of the strong force, which physicists have used for decades without proving it’s well-defined. It also bears on a Millennium Prize Problem.
On the positive side, suddenly there's a whole bunch of open problems!
Turning the question arouhnd: what would be the most impactful thing for OpenAI or Anthropic to do to show large breakthroughs?
ETH sounds more like there's a path it could become important? In general, the recent complexity results suggest that a) our intuitions about that world are unreliable, and b) the truth seems to be insanely complicated. I mean, new faster multiplication algorithms in 2026, what the hell? How can we say anything about the full space of all possible algorithms?
The new faster multiplication algorithms are both galactic, are they not?
It does not seem surprising to me at all that AI can find new galactic algorithms that are not of any direct use (at best they can guide us to find better solutions that are non-galactic).
What would be surprising and interesting is if AI can find a new floating point multiply-add that is 2X faster per operation than the current fastest chip implementations. That would immediately have billion+ dollar implications. The teams who already work on this have excellent approaches and invest enormous amounts into tiny improvements already; there are probably not much low-hanging fruit there (proponents of using AI for chip design improvements have impressive claims, but unclear that any of those really worked out in reality).
Or is such understanding reliant in experimentation because there are "hidden constants" we can't figure out with math alone?
Why haven't these theories had more impact on materials science? We use DFT and other greatly simplified approaches (with tremendous results) but still I suspect we are massively underperforming in terms of producing materials with useful properties.
> We are announcing three new discoveries in mathematics, computer science, and physics about harmonic analysis, complexity theory, and quantum field theory.
1. Local smoothing and the Kakeya conjecture
2. The Exponential Time Hypothesis is false
3. Existence of quantum chromodynamics and completions of the Standard Model
“ Honestly, nothing yet. This is a theoretical result, and it doesn't solve a real-world problem today.
*Why it won't change much in practice:* A running time like 2^(n/√log n) is "subexponential" on paper, but for real inputs it's still astronomically slow. For a few hundred variables it's no better than the brute-force methods we already have. Hidden constants in the exponent could also make it worse in practice. Real-world SAT solvers (the CDCL kind) already handle millions of variables on practical problems using heuristics, and this result doesn't replace them.
*Where SAT shows up in everyday life, indirectly:* - Verifying that chips (like the one in your phone) have no design bugs - Scheduling and logistics, like timetables, delivery routes, and airline crews - Software package dependency resolution - Security analysis and cryptography research
*What it could change over time:* - *Research direction:* Many problems were assumed to be hard because ETH says so. If ETH is false, researchers may find faster algorithms for them, and some of those could eventually matter in practice. - *Cryptography:* It doesn't break encryption, since the algorithm is still far too slow. But it could shift how people think about the hardness assumptions behind some security arguments. - *Theory of math and proof:* The Lean verification is also a notable example of AI-assisted, machine-checked mathematics.
So the "big deal" is mainly for computer scientists: a long-held belief about the limits of computation may be wrong. Any benefit to normal people would be long-term and indirect, and only if it leads to practical algorithms.“