

At Steklov Mathematical Institute of Russian Academy of Sciences
July 22, 2015 15:00, Moscow






Constraints, Graphs, Algebra, Logic, and Complexity
Moshe Vardi^{} 
Video records: 

MP4 
2,006.4 Mb 

MP4 
509.1 Mb 
Number of views: 
This page:  1036  Video files:  240 

Abstract:
A large class of problems in AI and other areas of computer science can be viewed as constraintsatisfaction problems. This includes problems in database query optimization, machine vision, belief maintenance, scheduling, temporal reasoning, type reconstruction, graph theory, and satisfiability. All of these problems can be recast as questions regarding the existence of homomorphisms between two directed graphs. It is wellknown that the constraintsatisfaction problem is NPcomplete. This motivated an extensive research program into identify tractable cases of constraint satisfaction.
This research proceeds along two major lines. The first line of research focuses on nonuniform constraint satisfaction, where the target graph is fixed. The goal is to identify those traget graphs that give rise to a tractable constraintsatisfaction problem. The second line of research focuses on identifying large classes of source graphs for which constraintsatisfaction is tractable. We show in this talk how tools from graph theory, universal algebra, logic, and complexity theory, shed light on the tractability of constraint satisfaction
Language: English

