February 16, 2007
Ryan Williams
1:30 PM, 1507 Newell-Simon Hall
Thesis Proposal
Title: Algorithms and Resource Requirements for Fundamental Problems
Abstract:
We establish more efficient methods for solving certain classes of NP-hard problems exactly, as well as methods for proving limitations on how quickly the same problems can be solved.
For example, in the Max-Cut problem, one is given a graph $G=(V,E)$ and integer $K$, and one wishes to determine if $G$ has a subset of vertices such that the number of edges leaving the subset is at least $K$. The trivial algorithm for Max-Cut runs in roughly $O(poly(n)\cdot 2^n)$ time, where $n$ is the number of vertices in $G$. Prior to our work, no better algorithm was known for the general case. Our results imply that Max-Cut can be solved in $O(\sqrt{3}^n) = O(1.74^n)$ time and space, yet Max-Cut cannot be solved in $O(n^{\sqrt{3}})$ time and $n^{o(1)}$ space.
Further study includes finding faster algorithms and proving larger limitations for these problems, as well as extending our techniques to counting versions of {\sf NP} problems. We have already extended some of our algorithms in this manner, and are currently working on how limitations can be proved.
Thesis Committee:
Manuel Blum, Chair
Ryan O’Donnell
Steven Rudich
Russell Impagliazzo, University of California, San Diego
Dieter van Melkebeek, University of Wisconsin, Madison
