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