Hacker News: isaacfrond

New comment by isaacfrond in "Fold Epic Paper Airplanes"

isaacfrond — Mon, 09 Nov 2026 12:55:40 +0000

Some reason being the AI messed up?

New comment by isaacfrond in "Efficient algorithms, the Exponential Time Hypothesis, and losing the plot"

isaacfrond — Tue, 03 Nov 2026 11:33:00 +0000

Moreover, it was already known that some NP-complete problems admit sub-exponential algorithms. For example, planar graph 3-colorability can be solved in 2^O(sqrt(n)) time. This is not only sub-exponential, but vastly better than the running time of the new 3-SAT algorithm.

Still, the result is very interesting, since many problems can be solved asymptotically faster once subproblems that can be represented as 3-SAT can be solved faster. For example, we now have now have a deterministic interger factoring algorithm with run time N^o(1), where N is the integer being factored. Heuristic algorithms already achieved this bound, but the new claim is a deterministic worst-case guarantee. The result is a fairly straightforward application of the new 3-SAT solver.

New comment by isaacfrond in "The 'else' keyword is probably a literal translation from German (2020)"

isaacfrond — Thu, 29 Oct 2026 06:16:21 +0000

It is nor far-fetched to suppose else is a translated German word because that is exactly what happened. The only question is which German word was is it.

New comment by isaacfrond in "The Exponential Time Hypothesis Is False [pdf]"

isaacfrond — Tue, 27 Oct 2026 11:01:28 +0000

Right. To be clear: the halting problem is not in the class NP. Any problem in NP can trivially be reduced to the halting problem and so the latter is NP-hard.

R/open source just banned AI, non-English speakers, and more

isaacfrond — Mon, 26 Oct 2026 14:22:31 +0000

Article URL: https://www.theverge.com/ai-artificial-intelligence/1018217/reddit-opensource-ai-ban

Comments URL: https://news.ycombinator.com/item?id=50244212

Points: 1

# Comments: 1

New comment by isaacfrond in "Navier–Stokes Lost in Translation"

isaacfrond — Thu, 08 Oct 2026 12:33:23 +0000

Which is exactly why you want a Lean proof in the first place!

NL proofs rely on not-entirely-correct prior art, and contain countless holes both big and small. When formalizing human NL proofs it is probably very normal that the Lean proofs doesn't quite follow the NL proof.

New comment by isaacfrond in "When Google Cuts Off Access: Poland and the World"

isaacfrond — Tue, 15 Sep 2026 13:57:05 +0000

I'd say it's totally immaterial how it was written

New comment by isaacfrond in "The Navier–Stokes Millennium Prize Problem"

isaacfrond — Wed, 09 Sep 2026 08:03:25 +0000

> Surely researchers like this have the processing power to run them at home,

Nobody has that power. Certainly not mathematicians.

A New Framework for How the Brain Compresses Our Noisy World

isaacfrond — Wed, 26 Aug 2026 07:51:51 +0000

Article URL: https://www.quantamagazine.org/a-new-framework-for-how-the-brain-compresses-our-noisy-world-20260824/

Comments URL: https://news.ycombinator.com/item?id=49445394

Points: 3

# Comments: 0

More than 100 suspicious images in Thermo Fisher antibody catalogue

isaacfrond — Wed, 26 Aug 2026 07:29:26 +0000

Article URL: https://www.nature.com/articles/d41586-026-01706-2

Comments URL: https://news.ycombinator.com/item?id=49445231

Points: 5

# Comments: 1

New comment by isaacfrond in "Ten advances in mathematics and theoretical computer science"

isaacfrond — Tue, 04 Aug 2026 12:50:36 +0000

The paper does not resolve P versus NP, but it does make an important advance in a closely related area. To prove that P ≠ NP, it would be enough to show that every algorithm for an NP-complete problem requires superpolynomial time. We cannot prove anything remotely that strong. For explicit NP-complete problems in unrestricted computational models, we cannot even prove superlinear lower bounds. There is therefore an enormous gap between the lower bounds we can prove and the superpolynomial bounds we would need.

VP and VNP are closely related algebraic analogues of P and NP. Here the paper proves new lower bounds for computing the permanent, a VNP-complete polynomial, in particular models of arithmetic computation: roughly (n^2\log\log n) arithmetic gates for unrestricted division-free circuits, and (n^4/\log n) size for the more restrictive formula model. These are still polynomial bounds, so they do not separate VP from VNP. But lower bounds on the resources needed to compute explicit functions are exactly what would ultimately be required for such a separation, and meaningful lower bounds of this kind are exceptionally rare.