Connections Between Pseudorandomness and an Area of CS that Cannot be Mentioned Here

Russell Impagliazzo (UC San Diego)

The very first thing Leonid Levin taught me was to avoid oxymorons. For example, individually ``automaton'' makes sense and ``non-deterministic'' makes sense, but to combine them is an oxymoron. Similarly, a very popular area of CS goes by a name that cannot be mentioned because it is an oxymoron using the Levin standard. This area would be most properly known as algorithmic extrapolation, since it seeks to use algorithms that are given function values at some inputs and extrapolates the values at other inputs. In a joint paper with myself from 1990, Leonid added a section showing very strong average-case algorithmic extrapolation would be efficient if there were no one-way functions. I will attempt to sketch the contents of this result without using forbidden phrases, and discuss certain consequences and refinements made by Blum, Furst, Kannan and Lipton and by Naor and Reingold. I will then discuss how this idea has been used in a line of work starting with Li and Pass to characterize the existence of one-way functions in terms of the average-case complexity of meta-complexity problems. If time permits, other connections between algorithmic extrapolation and pseudo-randomness will be discussed.