91
Nearly All Binary Searches and Mergesorts Are Broken (2006)
Posted by Joshua Bloch, Software EngineerI remember vividly Jon Bentley's first Algorithms lecture at CMU, where he asked all of us incoming Ph.D. ...
Most cited
Posts that commenters keep linking to, ranked by how many different people have cited them in Hacker News comments. 494 posts.
92
Energy Is Not Conserved (2010)
I’ve been meaning to link to this post at the arXiv blog , which is a great source of quirky and interesting new papers. In this case they are pointing to a speculative but interesting paper by Martin Perl and Holger Mueller, which suggests an experimental search for gradients in dark energy by way of atom…
93
Announcing the first SHA-1 collision
Posted by Marc Stevens (CWI Amsterdam), Elie Bursztein (Google), Pierre Karpman (CWI Amsterdam), Ange Albertini (Google), Yarik Markov (Goog...
94
An OpenAI model has disproved a central conjecture in discrete geometry
An OpenAI model solved the 80-year-old unit distance problem, disproving a major conjecture in discrete geometry and marking a milestone in AI-driven mathematics.
95
96
Math For Programmers
Probability theory might be the most useful area for programmers, but it is also a blurry field, difficult to learn right. You might check this book for details, and there is also an free, online draft version available. The Logic of Science
97
The 8000th Busy Beaver number eludes ZF set theory (2016)
I’ve supervised a lot of great student projects in my nine years at MIT, but my inner nerdy teenager has never been as personally delighted by a project as it is right now. To…
98
Let’s talk about PAKE
The first rule of PAKE is: nobody ever wants to talk about PAKE. The second rule of PAKE is that this is a shame, because PAKE — which stands for Password Authenticated Key Exchange — is actually o…
99
A fast alternative to the modulo reduction (2016)
Suppose you want to pick an integer at random in a set of N elements. Your computer has functions to generate random 32-bit integers, how do you transform such numbers into indexes no larger than N? Suppose you have a hash table with a capacity N. Again, you need to transform your hash values (typically 32-bit ……
100
A Mathematical Framework for Transformer Circuits (2021)
Transformer language models are an emerging technology that is gaining increasingly broad real-world use, for example in systems like GPT-3 , LaMDA , Codex , Meena , Gopher , and similar models. However, as these models scale, their open-endedness and high capacity creates an increasing scope for unexpected and…
101
Regular Expression Matching in the Wild
The first two articles in this series, “ Regular Expression Matching Can Be Simple And Fast ” and “ Regular Expression Matching: the Virtual Machine Approach ,” introduced the foundation of DFA-based and NFA-based regular expression matching. Both were based on toy implementations optimized for teaching the basic…
102
Viktor T. Toth
This page contains a JavaScript calculator of Hawking radiation and other parameters of a Schwarzschild black hole.
103
Backblaze Releases the Reed-Solomon Java Library for Free
Today we are releasing our latest open-source project: Backblaze Reed-Solomon Java library for erasure coding. Click for details on how to use and download.
104
The Patriot Missile Failure
On February 25, 1991, during the Gulf War, an American Patriot Missile battery in Dharan, Saudi Arabia, failed to track and intercept an incoming Iraqi Scud missile. The Scud struck an American Army barracks, killing 28 soldiers and injuring around 100 other people. A report of the General Accounting office…
105
The Three Projections of Doctor Futamura
Introduction The Three Projections of Futamura are a sequence of applications of a programming technique called 'partial evaluation' or 'sp...
106
Chicago undergraduate mathematics bibliography
Somehow I became the canonical undergraduate source for bibliographical references, so I thought I would leave a list behind before I graduated. I list the books I have found useful in my wanderings through mathematics (in a few cases, those I found especially un useful), and give short descriptions and comparisons…
107
1/0 = 0
Disclaimer 2024-12-02 Since this rant is going viral again (again (again)), some disclaimers: I wrote this six years ago to “”“win”“” an ugly Twitter fight. I’m glad I anonymized the inciting tweet and hope I’m the only person still getting grief over this. The core interesting bit— why it’s mathematically valid to…
108
An Interactive Introduction to Fourier Transforms
Fourier transforms are a tool used in a whole bunch of different things. This is a explanation of what a Fourier transform does, and some different ways it can be useful.
109
Deciphering the Business Card Raytracer
I recently came across Paul Heckbert's business card raytracer. For those that have never heard of it: It is a very famous challenge in the Computer Graphics field that started on May 4th, 1984 via a post on comp.graphics by Paul Heckbert ( More about this in his article " A Minimal Ray Tracer " from the book Graphics…
110
111
Deep Learning, NLP, and Representations
neural networks , deep learning , representations , NLP , recursive neural networks
112
Division by zero in type theory: a FAQ
How can a theorem prover use the convention that 1/0=0 and still be consistent?
113
Correlation is usually not causation. But why not?
Correlations are oft interpreted as evidence for causation; this is oft falsified; do causal graphs explain why this is so common, because the number of possible indirect paths greatly exceeds the direct paths necessary for useful manipulation?
114
The Superinvestors of Graham-and-Doddsville (1984)
Columbia Business School. For over 100 years, we’ve helped develop leaders who create value for business and society at large.
115
Torsors (2010)
When you first read about "torsors", they're bound to seem a bit too darn sophisticated for their own good. Mostly this is because nobody explains them very well. So, I want to convince you that they're actually very simple and natural. I'll do this by giving you three examples from physics:
116
Rationality: From AI to Zombies
A series by Eliezer Yudkowsky
117
On Vigna's PCG Critique
On 14 May 2018, Sebastiano Vigna added a page to his website (archived here) entitled “The wrap-up on PCG generators” that attempts to persuade readers to avoid various PCG generators. That day, he al
118
Peter Selinger: MD5 Collision Demo
C:\TEMP> md5sum hello.exe cdc47d670159eef60916ca03a9d4a007 C:\TEMP> .\hello.exe Hello, world! (press enter to quit) C:\TEMP>
119
Schelling's Model of Segregation
Racial segregation has always been a pernicious social problem in the United States. Many factors have contributed to segregation including prejudice, zoning laws, housing discrimination, and loan discrimination. Although much effort has been extended to desegregate our schools, churches, and neighborhoods, the US…
120
Why haven't quantum computers factored 21 yet?
Craig Gidney's computer science blog