Universiteit van Amsterdam

Events

Institute for Logic, Language and Computation

Please note that this newsitem has been archived, and may contain outdated information or links.

7 September 2006, PhD defense, Robert Spalek

Candidate: Robert Spalek
Title: Quantum Algorithms, Lower Bounds, and Time-Space Tradeoffs
Date: Thursday 7 September 2006
Time: 12:00
Location: Oude Lutherse Kerk, Singel 411, Amsterdam
Promotor: Harry Buhrman
Copromotor: Ronald de Wolf

In this thesis, we investigate fast quantum algorithms for several graph problems (such as finding a maximal bipartite matching, and a maximal flow in an integer network) and verification of matrix products. We also address quantum query lower bounds, i.e. proofs that certain tasks cannot be computed faster than some value. We prove the first known time-space tradeoffs for quantum computation, and most of them are tight.

For more information, see http://www.ucw.cz/~robert/papers/abs-phd-en.html

Please note that this newsitem has been archived, and may contain outdated information or links.