Ronald de Wolf (CWI Amsterdam): Quantum proofs for classical theorems
In the last decade the theory of quantum mechanical computers
has developed, and we now know that quantum computers can be
exponentially faster than classical computers when solving certain
problems (probably including integer factoring). A more recent and
very different application of quantum computers is as a mathematical
tool to prove or reprove theorems about classical computers. We will
give three examples, from the areas of communication complexity, matrix
rigidity, and locally-decodable error-correcting codes. In addition,
for the latter case we will describe a very recent and interesting new
classical code construction due to Yekhanin, based on Mersenne primes.
Combining his result with our techniques gives very efficient quantum
"private information retrieval systems".