American Institute of Mathematics, Palo Alto, California
Anuj Dawar, Phokion Kolaitis, Benoit Larose, and Matt Valeriote
This workshop, sponsored by AIM and the NSF, will be devoted to advancing the understanding of the computational complexity of the constraint satisfaction problem using methods and techniques from universal algebra and logic. The intended participants are researchers in computational complexity, universal algebra, and logic. By bringing together researchers from these three areas, progress could be made towards resolving long-standing open problems about the complexity of constraint satisfaction. The most prominent such problem is the Dichotomy Conjecture formulated by Feder and Vardi in 1993, which asserts that, for every constraint language C over an arbitrary finite domain, either the constraint satisfaction problem CSP(C) is in P or it is NP-complete.
The main topics for the workshop are:
This conjecture, which has been formulated by Bulatov, Jeavons, and Krokhin, refines the Feder-Vardi Dichotomy Conjecture by suggesting a classification of the complexity of constraint satisfaction in terms of universal algebra.
The workshop will differ from typical conferences in some regards. Participants will be invited to suggest open problems and questions before the workshop begins, and these will be posted on the workshop website. These include specific problems on which there is hope of making some progress during the workshop, as well as more ambitious problems which may influence the future activity of the field. Lectures at the workshop will be focused on familiarizing the participants with the background material leading up to specific problems, and the schedule will include discussion and parallel working sessions.
The deadline to apply for support to participate in this workshop has passed.
For more information email email@example.com
Plain text announcement or brief announcement.
Go to the
American Institute of Mathematics.
Go to the list of upcoming workshops.