computationalcomplexity

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 Problem.

--------------------------------------------------------------------

THE ERDŐS DISTINCT DISTANCE PROBLEM

A nice high school math competition problem, if it were not fairly well known, is:

Show that for a...

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 length \(n\) than \(m\), \(f\) is not onto. Can you find a string not in the range? This is known as the range avoidance problems, or AVOID for short 

Let's do an example. Consider \(f\) that outputs an undirected graph on \(n\)...

 1) Congratulations to Scott Aaronson for winning the first Trevisan Award.

The Trevisan Award is in memory of Luca Trevisan and recognizes expository work in TCS. It is given out by the ACM. The ACM announcement of Scott's award is here. Scott blogged...

For those very long-time readers this blog extensively covered prediction markets from 2006 to 2008. In a prediction market, you have a future event, such as the winner of an election, and a market that pays off one dollar if that event...

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

I wondered if it was still in print and could be bought:

1) I went to Amazon a...