Computational Complexity

The technical paper for the Erdős Unit Distance Problem lists only "OpenAI" as an author. When Bill posted on Sunday about the E...

In a 1946 paper in the American Mathematical Monthly, Paul Erdős posed the Erdős Distinct Distance Problem and the Erdős Unit Distance Probl...

Let \(f\) be a function mapping binary strings of length \(m\) to strings of length \(n\) with \(n>m\). Since there are more strings of l...

 1) Congratulations to Scott Aaronson for winning the first Trevisan Award. The Trevisan Award is in memory of Luca Trevisan and recognizes ...

For those very long-time readers this blog extensively covered prediction markets  from 2006 to 2008. In a prediction market, you have a fut...

In David Marcus's guest post on good coding style (see  here )  he reviewed a book from 1986 called  "Professional Pascal." I ...

As the blog of record in computational complexity, we like to bring attention to those in the community who have left us. When we learn of s...

Michael Rabin passed away on April 14,2026. I blogged about him  here .  My post listed results of his that proved upper and lower bounds on...