[Colloquium] [Staff] Theory Seminars at Computer Science

[Donna Brooms]

~REMINDER~
Date:         Tuesday, April 17,  2012
Time:        3 p.m.
Place:        Ryerson 251, 1100 E. 58th Street
_________________________ 
Speaker:    Gabor Kun
From:        New York University
Title:         Constraint Satisfaction Problems and expander relational structures
Abstract:   In their seminal paper Feder and Vardi proved that every problem in the class Monotone Monadic Strict NP (MMSNP) is random polynomial-time equivalent to a finite union of Constraint Satisfaction Problems (CSP). The class MMSNP is the "largest natural" subclass defined by syntactical restrictions on existential, second order formulas that might have the dichotomy property. This was the main reason for the famous dichotomy conjecture of Feder and Vardi for CSP problems
We derandomize their reduction showing that every MMSNP problem is `polynomial-time equivalent to a finite union of CSP problems. The technical novelty of the paper is a notion of expander relational structures. We give a polynomial-time construction of such structures with large girth. We show another interesting application of these structures: we give an effective construction of hypergraphs with large girth and chromatic number.
*Refreshments will be served prior to the talk at 2:30 in Ryerson 255*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20120417/1f3db8d3/attachment.htm