Title: Local Optimization on Graphs: Deterministic, Randomized and Quantum


			     Mario Szegedy
			   Computer Sciences
			   Rutgers University
			 110 Frelinghuysen Road
			  Piscataway, NJ 08854
		       szegedy@dragon.rutgers.edu
		   http://athos.rutgers.edu/~szegedy


Abstract:
Let f be an integer valued function on a finite set V. We call an undirected 
graph G(V,E) a neighborhood structure for f. The problem of finding a local 
minimum for f can be phrased as: for a fixed neighborhood structure G(V,E) 
find an input x in V such that f(x) is not bigger than any value that f takes 
on some neighbor of x. The complexity of the algorithm is measured by the 
number of questions of the form ``what is the value of f on x?'' We show that 
the deterministic, randomized and quantum query complexities of the problem 
are polynomially related. This generalizes earlier results of Aldous and 
Aaronson and solves the main open problem raised by the latter author.        
(joint with Miklos Santha)