[Colloquium] Correction: Guest Speakers @ TTI-C THIS Week(2/27/06-3/3/06)

[Katherine Cumming]

There has been a change to the schedule of speakers this week at TTI-C.
Ryan O'Donnell will not be speaking at TTI-C on Tuesday, February 28;
however, he will speak at the University of Chicago Computer Science
Department (Ryerson 251) on Wednesday, March 1 at 2:30 pm.
 
Please see:  http://www.cs.uchicago.edu/events for more information.  
 
 
  _____  

***SCHEDULE CHANGE***
 
 (2)
 
Speaker:  Ryan O'Donnell, Microsoft Research Theory Group
Speaker's home page: http://research.microsoft.com/~odonnell/
 
Date: Wednesday, March 1, 2006 
Location: Ryerson 251
Time:  3:00pm
 
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 over constrained 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: $87.8567 \dots$\%. 
 
 
 
----------------------------------------------------------------------------
------
If you have questions, or would like to meet the speaker, please contact
Katherine at 773-834-1994 or kcumming at tti-c.org.   
For information on future TTI-C talks and events, please go to the TTI-C
Events page:  http://www.tti-c.org/events.html.  TTI-C (1427 East 60th
Street, Chicago, IL  60637)
 
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20060227/83153972/attachment.htm