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:  $87.8567 dots

Monday , March 27, 2006

337 Towne Bldg

3:00pm - 4:15 pm