|
|
Title: Long Code Tests and the Dichotomy Conjecture for CSPs |
Name: Mario Szegedy Rutgers University |
|
| Time:October 14th (Tuesday) 16:00-16:45 | |
| Location: Lecture Hall, FIT Building, Tsinghua University | |
| Host Unit: ITCS, Tsinghua University |
|
|
Title: Long Code Tests and the Dichotomy Conjecture for CSPs |
Name: Mario Szegedy Rutgers University |
|
| Time:October 14th (Tuesday) 16:00-16:45 | |
| Location: Lecture Hall, FIT Building, Tsinghua University | |
| Host Unit: ITCS, Tsinghua University |
The dichotomy conjecture of Feder and Vardi states that every constraint satisfaction problem is either NP complete or polynomial time solvable. Some special cases of the conjecture are settled. Shaeffer has a solution, when the underlying alphabet is binary, which was generalized by Bulatov for trinary alphabets. Hell and Nesetril have proved the conjecture, when the CSP contains a single binary symmetric relation.
We establish a three ways connection between the dichotomy conjecture, the type of long code tests used in the theory of PCPs and between higher order dynamical systems. Using this relation we give a simple proof for the Hell Nesetril theorem binding it to a recent result of Dinur, Friedgut and Regev.
This is joint work with Gabor Kun.Mario Szegedy is a professor of computer science at Rutgers University. He received his Ph.D. in computer science in 1989 from the University of Chicago. Szegedy's research areas include complexity theory, combinatorITCS and quantum computing. He was awarded the Godel Prize twice, in 2001 and 2005, for his work on probabilistically checkable proofs and on the space complexity of approximating the frequency moments in streamed data.
