Ryan O’Donnell, MIT/Microsoft Theory Group
Feb 20, 2006
NSH 3305, 1:30pm
Abstract:
For most constraint satisfaction problems — such as finding the maximum cut in a graph, or trying to solve an overconstrained system of equations — it is NP-hard to find an optimal solution. Nevertheless, one still wants to find algorithms that come as close to the optimum as they can. Unfortunately, the best known algorithms and the best known NP-hardness results do not yet match for many basic problems.
In this talk I will talk about recent attempts to find the sharp boundaries between P and NP for approximating constraint satisfaction problems. Interestingly, progress on proving hardness results mostly comes by finding more efficient algorithms in the area of “property testing”. I will describe new such algorithms and mention how their analysis is connected to such diverse areas as voting theory and the “double bubble” problem. As an example consequence of these connections, we get complexity-theoretic evidence that there is no efficient algorithm for finding the maximum cut in a graph with guarantee better than Goemans-Williamson’s: 0.878567….
BIO: Ryan O’Donnell received his Ph.D. from MIT in 2003, advised by Madhu Sudan. He then went to the Institute for Advanced Study as a postdoc under Avi Wigderson and is currently a postdoc at Microsoft Research. Ryan received a Best Student Paper award at CCC for his paper “Hardness amplicification within NP” and a Best Paper award for his paper “Extremal properties of polynomial threshold functions”. His research focus is on complexity theory, hardness of approximation, discrete fourier analysis, and computational learning theory.
