[Colloquium] Talk by Ryan O'Donnell on March 1, 2006

[Margery Ishmael]

DEPARTMENT OF COMPUTER SCIENCE - TALK

Date: Wednesday, March 1, 2006
Time: 2:30 p.m.
Place: Ryerson 251

-------------------------------------------

Speaker:  RYAN O'DONNELL

From:  Microsoft Research Theory Group

Url:  http://research.microsoft.com/%7Eodonnell/

Title:  Constraint Satisfaction and Property Testing

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 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  
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.

***The talk will be followed by refreshments in Ryerson 255***

-------------------------------------------------------

Host:  Lance Fortnow

People in need of assistance should call 773-834-8977 in advance.

For information on future CS talks, please see: http:// 
www.cs.uchicago.edu/events


-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20060215/bee1d213/attachment.htm