271
Damn Cool Algorithms: Levenshtein Automata
Posted by Nick Johnson | Filed under python , tech , coding , damn-cool-algorithms
Most cited
Posts that commenters keep linking to, ranked by how many different people have cited them in Hacker News comments. 494 posts.
272
273
What Is Spacetime, Really?
On the 100th anniversary of Einstein’s Theory of Relativity, Stephen Wolfram discusses the nature of space and time, and fundamental theory of physics.
274
A Mechanistic Interpretability Analysis of Grokking
Neel Nanda reverse engineers neural networks that have "grokked" modular addition, showing that they operate using Discrete Fourier Transforms and tr…
275
A proof that Unix utility sed is Turing complete
Many people are surprised to learn that `sed`, a seemingly simple text filtering program, is actually Turing complete. This realization prompts the question: how can a text processing utility achieve such computational power? The answer lies in sed's fundamental operations. Essentially, sed functions as a miniature...
276
277
Java Hangs When Converting 2.2250738585072012e-308
Konstantin Preißer made an interesting discovery , after reading my article “ PHP Hangs On Numeric Value 2.2250738585072011e-308 ”: Java — both its runtime and compiler — go into an infinite loop when converting the decimal number 2.2250738585072012e-308 to double-precision binary floating-point. This number is…
278
279
Is Extended Random a Malicious NSA Plot?
Dual_EC was almost certainly an NSA backdoor. Extended Random is the TLS extension that would have made it practical to exploit. Did NSA plant that one too? A look at the evidence.
280
TreeMaker: Origami Design Software
In 1989, I wrote an article for the magazine Engineering & Science about the state of technical folding, which, even then, seemed to be progressing by leaps and bounds due to an infusion of scientific and mathematical principles. In recounting some of the connections between origami, math, and technology, I wrote:
281
Optimizing things in the USSR (2016)
A review of Red Plenty, by Francis Spufford
282
Three-Valued Logic
Making decision despite missing SQL data (NULL): How to avoid OR…IS NULL in the WHERE clause.
283
The case against geometric algebra (2024)
Every once in a while the internet gets talking about Geometric Algebra (henceforth GA) and how it’s a new theory of math that fixes everything that’s wrong with linear algebra and multivariable calculus. When I come across this stance I am compelled to respond with something like: “wait wait, it’s not true! GA is…
284
Quasi-Polynomial Algorithm for Graph Isomorphism
Update (Dec. 14): The long wait is over! Here’s Laci’s paper on the arXiv. So far, I’ve read it only deeply enough to note that it contains the following sentence: A group G ≤ S…
285
Trapped priors as a basic problem of rationality
P(A|B) = [P(A)*P(B|A)]/P(B), all the rest is commentary.
286
Understanding is a poor substitute for convexity (2012)
Something central, very central, is missing in historical accounts of scientific and technological discovery. The discourse and controversies focus on the role of luck as opposed to teleological programs (from telos, "aim"), that is, ones that rely on pre-set direction from formal science. This is a faux-debate: luck…
287
Rathbun's Operator
First, I’m a human typing this post. I’m not going to tell you who I am. Sure, many will say that is cowardly and fair, but I actually don’t think it would bring much value. What matters more is that I describe why, and what I did and didn’t do during the last two weeks or so with the OpenClaw agent I set up, known as…
288
There's Math.random(), and then there's Math.random() (2015)
V8’s Math.random implementation now uses an algorithm called xorshift128+, improving the randomness compared to the old MWC1616 implementation.
289
Insert D-Wave Post Here
In the two months since I last blogged, the US has continued its descent into madness. Yet even while so many certainties have proven ephemeral as the morning dew—the US’…
290
Smaller than Bloom filters
I've been looking at what would be needed in order to have a global view of CRLs in browsers. At the moment revocation has three problems: privacy (by asking the CA about the status of a certificate you're revealing to them what you're looking at), performance (OCSP checks take hundreds of milliseconds which adds up…
291
292
The Map Is Not the Territory (2015)
The map is not the territory reminds us that our mental models of the world are not the same as the world itself. It cautions against confusing our abstractions and representations with the complex, ever-shifting reality they aim to describe.
293
Ultimate Tic Tac Toe
Once at a picnic, I saw mathematicians crowding around the last game I would have expected: Tic-tac-toe.
294
Deep image prior 'learns' on just one image
Deep convolutional networks have become a popular tool for image generation and restoration. Generally, their excellent performance is imputed to their ability to learn realistic image priors from a large number of example images. In this paper, we show that, on the contrary, the structure of a generator network is…
295
296
Ten advances in mathematics and theoretical computer science
OpenAI shares new results on long-standing open problems in mathematics and theoretical computer science, including advances in geometry, cryptography, and complexity.
297
Decision trees – the unreasonable power of nested decision rules
An introduction to the Decision Trees, Entropy, and Information Gain.
298
299
Gemini with Deep Think achieves gold-medal standard at the IMO
The International Mathematical Olympiad (“IMO”) is the world’s most prestigious competition for young mathematicians, and has been held annually since 1959. Each country taking part is represented by six elite, pre-university mathematicians who compete to solve six exceptionally difficult problems in algebra…
300
Eigenvectors and eigenvalues explained visually
Eigenvalues/vectors are instrumental to understanding electrical circuits, mechanical systems, ecology and even Google's PageRank algorithm. Let's see if visualization can make these ideas more intuitive.