Tag Archives: average-case complexity

Impagliazzo’s Multiverse

Update (July 2009): Here are links to a related post on Lipton’s blog, and a conference announcement on Russell’s possible worlds.

On the occasion of Luca’s post on his FOCS 2008 tutorial on average-case complexity here is a reminder of Russell Impagliazzo’s description of the possible universes we live in.

Being at FOCS was a splendid experience and my presentation of the paper of Ehud Friedgut, Noam Nisan and myself was well accepted. (And reported by Rahul Santhanam on “Computational Complexity“) The slides are here; Initially I felt bad for including only one out of three parts of the proof but eventually I had no time to describe any part of the proof.

Russell Impagliazzo’s multiverse – cryptography and complexity

Impaglliazzo’s paper deals with two central topics in theoretical computer science: Computational complexity studies the power of computers and cryptography studies the ability to create codes and to hide information. These two areas added beautiful new scientific insights, and the deep connections between them were described by computer scientist Shafi Goldwasser as “a match made in heaven.” The limited power of computers and the well known question “whether P=NP” are of central importance in Impaglliazzo’s classification,  as are the concepts of “one way functions” and “public keys”.


In this universe computers can quickly solve hard problems.  (In technical terms: P=NP.)  If you can quickly recognize a valid solution to a problem once the latter is presented to you,  (such problems are “in NP”), then you can apply this same method in order to actually find a solution! In this universe almost all optimization problems have a quick and automatic solution. No cryptography is possible and therefore there is no privacy.


Muhammad ibn Musa al-Khwarizmi (the term “algorithm” is called after his name, and not after All Gore as commonly believed)


In this universe Continue reading