[Colloquium] THEORY SEMINAR REMINDER

[Donna Brooms]

DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF CHICAGO
Date:  Tuesday, April 12, 2011
Time:  3pm
Place:  Ryerson 251
----------------------------------------------
Speaker: Gabor Kun
http://www.mathc.rwth-aachen.de/kun/
From: New York University
Title: An analytic approach to the dichotomy conjecture
Abstract: The dichotomy conjecture of Feder and Vardi states that every Constraint Satisfaction Problem is either tractable or NP-complete. The nicest proved case is the Hell-Nesetril theorem: the H-coloring (homomorphism) problem is tractable if H is bipartite and NP-complete else. We show an analytic approach to the dichotomy conjecture. We give a transparent proof of the Hell-Nesetril theorem demonstrating this approach.
Joint work with Mario Szegedy.
Host: Prof. Laszlo Babai                                                                                                                                      Refreshments will be served prior to the talk at 2:30 in Ryerson 255                                                                                                                                                                 Persons who need assistance should call 773-702-6614
 

 

 
 

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