September 2011 October 2011 November 2011 Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa 1 2 3 1 1 2 3 4 5 4 5 6 7 8 9 10 2 3 4 5 6 7 8 6 7 8 9 10 11 12 11 12 13 14 15 16 17 9 10 11 12 13 14 15 13 14 15 16 17 18 19 18 19 20 21 22 23 24 16 17 18 19 20 21 22 20 21 22 23 24 25 26 25 26 27 28 29 30 23 24 25 26 27 28 29 27 28 29 30 30 31 |

4:00 pm Monday, October 10, 2011 Computer Science Colloquium: The Mathematics of Constraint Satisfactionby
Matt Valeriote (McMaster University) in Keck 100- A reception will be held beginning at 3:30 PM in Duncan Hall, Room 3076.
Many important problems from combinatorics, logic, and computer science can be expressed as instances of the constraint-satisfaction problem (CSP). For example, instances of graph k-colorability for some k and instances of boolean satisfiability can be regarded as CSPs. While the class of constraint-satisfaction problems is known to be NP-complete, there are many natural subclasses of it that are tractable. It is conjectured by Feder and Vardi that in fact any such naturally defined subclass is either tractable or is NP-complete. In my talk I will introduce the class of CSPs and then discuss an approach via algebra to settle the Feder-Vardi Dichotomy Conjecture. Submitted by hassett@math.rice.edu |