I got my BSc degree from the Computer Science and Engineering Department of the University of Patras, Greece back in 1990 and my MSc and PhD degrees from the University of California, San Diego in 1993 and 1996, respectively. My PhD advisor was Russell Impagliazzo.
Title: "Go With The Winners" Algorithms: A Rigorous Analysis and a New Framework for Optimization".
Description: It is the first time an attempt is being made to find the conditions under which a general optimization algorithm can be used to solve problems that troubled researchers for more than two decades. The novelty of this approach is to view the combinatorial structure of the space of solutions as the key idea to understanding the behavior of optimization heuristics. These algorithms are based mainly on intuition or experience and their effectiveness and efficiency have never been analyzed in a satisfactory manner. In particular, very little is known about the types of problems for which they do well, the tradeoff between optimality of the solution found and time spent searching, or how to set the various parameters optimally. This work is the first that attempts to provide a causal connection between the combinatorial structure of these problems and the success of these algorithms and give insight into which problems might be susceptible to a randomized optimization algorithm of wide applicability.
Advisor: Prof. Russell Impagliazzo