Date: Tuesday 28 February

Who: Robert Spalek

Seminar type: Tutorial Seminar

Time: 4-5pm

Where: Conference Room

Abstract:
Let P be the class of problems computable in polynomial time, for example finding a shortest path in a graph, multiplying two matrices, or finding an optimal solution of a linear or semidefinite program. Let BPP be the class of problems computable in polynomial time with bounded error using random coin flips. We require that for every possible input, the probability of getting the right outcome is at least 2/3.
Computer scientists used to strongly believe that P != BPP. Recently, Agrawal, Kayal, and Saxana showed a breakthrough result that testing whether a given number is prime can be done in time polynomial in the number of digits. This problem had been a good candidate for something that is in BPP but not in P, since several randomized algorithms for this problem were known for decades. A few decades ago, before the discovery of the elipsoid method and the interior method, linear programming had been another such example. Are we having a shortage of non-trivial randomized algorithms?

Nisan and Wigderson showed in 1994 a ground-breaking result that the existence of a hard function implies the existence of good pseudorandom generators. A pseudorandom generator (PRG) is an algorithm that takes a sequence of K bits and produces a longer sequence, say of length L=2^K.
We say a PRG is good if it fools every polynomial algorithm, that is no polynomial-time algorithm can distinguish whether it got a truely random sequence or a sequence output by the PRG. The implication of this is that to derandomize (i.e. run deterministically without error and without the need for random bits) an algorithm that uses L random bits we don’t need to average over all 2^L choices, but only over all possible random pools of length K=log L, which takes polynomial time L=2^K. Hence every polynomial randomized algorithm can be simulated deterministically in polynomial time.

The result of Nisan and Wigderson implies that at least one of the two following plausible statements, long believed to be true, is wrong:

(a) there is at least one hard function
(b) randomness helps

What would you bet on?

Date: Friday 17th February

Who: Robert Špalek

Seminar type: Research Seminar

Time: 12 Midday

Where: Interaction Room

Abstract:
A time-space tradeoff is a relation between the running time and the space complexity of an algorithm. “The more memory is available, the faster the algorithm can possibly run.” I will present a quantum algorithm for deciding systems of linear inequalities, and show that the time-space tradeoff of this algorithm is optimal up to a poly-log factor. This is one of the few known time-space tradeoffs for quantum computation.

The main lower-bound technique is a so-called strong direct product theorem (DPT) for symmetric functions. A DPT says that to compute k independent instances of a problem, one needs k times more resources (e.g. time) than to compute one instance. Moreover, if the amount of available resources is a little smaller, then the success probability of computing everything right goes down exponentially with k. This intuitive statement is quite hard to prove and we only have it for symmetric functions.

* (joint work with Andris Ambainis and Ronald de Wolf, to appear in STOC’06, quant-ph/0511200)

Date: Tuesday 14 February

Who: Robert Špalek

Seminar type: Tutorial Seminar

Time: 4-5pm

Where: Conference Room

Abstract:
Quantum computers can search an unsorted database of size N in time sqrt(N) [Grover, 1996]. This search algorithm is very universal and one can use it as a subroutine for solving a number of other problems, for example element distinctness, that is testing whether all number in a sequence of length N are distinct, in time N^{3/4}. Ambainis [2004] published a very elegant algorithm based on quantum random walks solving this problem in time N^{2/3}, which is optimal. Szegedy [2004] generalized his quantum walk technique to all symmetric Markov chains and simplified the proof. The resulting algorithm is almost as universal as unsorted search, and it was successfully applied to triangle finding in time N^{1.3} [Magniez, Santha, Szegedy, 2005], group commutativity testing in time N^{2/3} [Magniez, Nayak, 2005], and verification of matrix products [Buhrman, Špalek, 2006].

I am going to talk about these quantum walk algorithms.