Titles and AbstractsSpeaker: Albert Atserias, Universitat Politecnica de Catalunya Title: Finite Model Theory and CSPs Download the slides of this talk here. Speaker: Manuel Bodirsky, Humboldt University, Berlin, Germany Title: Algebraic Tractability Criteria for Infinite-Domain CSPs Abstract: Several tractable classes of constraint satisfaction problems over infinite domains can be characterized by the existence of polymorphisms of the constraint language. In this talk I will show how polymorphisms can be used to find maximal tractable subclasses of constraint languages with a rich enough automorphism group, and provide auniversal-algebraic perspective on existing tractability results in spatial and temporal reasoning. Download the slides of this talk here. Speaker: Andrei Bulatov, Simon Fraser University Title: Coloured Graphs and Algebras Download the slides of this talk here. Speaker: Hubie Chen, University Pompeu Fabra, Spain Title: Quantified Constraint Satisfaction and the Polynomially Generated Powers Property Abstract: Consider the following property on algebras: an algebra A has the polynomially generated powers (PGP) property if there is a polynomial-size (in n) generating set for A^n. That is, A has the PGP if for each n there exists a subset X of A^n of polynomial (in n) size such that the smallest subalgebra of A^n containing X is A^n itself. This is a natural combinatorial property of algebras which, interestingly, has a strong connection to the complexity of quantified constraint satisfaction--the generalization of constraint satisfaction where universal quantification is permitted in addition to existential quantification. In this talk, I will give an overview of this connection and discuss recent progress on both understanding this property and the complexity of quantified constraint satisfaction. The following is a link to a paper that is related to the material presented in this talk: http://arxiv.org/abs/cs.LO/0607106 Speaker: Victor Dalmau, Universitat Pompeu Fabra Title: The Complexity of the Counting CSP Download the slides of this talk here. Speaker: László Egri, McGill University, Canada Title: Linear Datalog is not equal to Symmetric Datalog Abstract Download the slides of this talk here. Speaker: Andrei Krokhin, University of Durham, England Tutorial title: Algebraic approach to CSP: the basics Abstract: In this tutorial, I will demonstrate how to translate questions about the computational complexity of the CSP into questions about algebras and varieties. I will show how well-known universal-algebraic results and techniques can immediately give a deep insight into the computational structure of the CSP. Short algebraic proofs of some celebrated computational results will be given. Download the slides of this talk here. Speaker: Fredrik Kuivinen, Linköpings Universitet, Sweden Title: Excluding Polynomial-time Approximation Schemes for Max Csp Abstract Download the slides of this talk here. Speaker: Gabor Kun, University of Memphis, USA Abstract: We show that every NP problem is polynomially equivalent to a simple combinatorial problem: the membership problem for a special class of digraphs. These classes are defined by means of shadows and by finitely many forbidden colored subgraphs. Our characterization is motivated by the analysis of syntactical subclasses with the full computational power of NP, which were first studied by Feder and Vardi. Our approach applies to many combinatorial problems and it induces the characterization of coloring problems (CSP) defined by means of shadows. This turns out to be related to dualities. We give several applications concerning the class MMSNP, local chromatic number of graphs. Particularly, we show a surprising richness of coloring problems when restricted to most frequent graph classes. Even for bounded expansion classes (which include bounded degree and proper minor closed classes) holds that the restriction of every class defined as the shadow of finitely many colored subgraphs equals to the restriction of a coloring (CSP) class. Joint work with Jarik Nesetril. The following are links to some papers related to this talk: http://www.arxiv.org/abs/0706.3549 http://www.arxiv.org/abs/0706.1704 http://www.arxiv.org/abs/0706.1701 Speaker: Benoît Larose, Champlain Regional College, Canada Title: TCT, fragments of Datalog and the fine-grained complexity of CSP Abstract: To each fixed-target CSP is naturally associated a finite algebra. We outline various results that exhibit an interesting connection between (a) the typeset of the variety generated by this algebra, (b) the expressibility of the CSP in various fragments of Datalog and (c) membership of the CSP in complexity classes such as L, NL, mod_p L and P. Download the slides of this talk here. Speakers: Ralph McKenzie (Part I) and Miklos Maroti (Part II) Title: Existence of weakly symmetric operations, I and II: verifying an algebraic consequence of the CSP dichotomy conjecture Abstract Speaker: Petar Marković, University of Novi Sad, Serbia Title: Algebras with few subpowers are tractable Abstract Download the slides of this talk here. Speaker: Pascal Tesson, Laval University Title: Solving Systems of Equations over Finite Semigroups: a Case Study for CSPs Download the slides of this talk here. Speaker: Moshe Vardi, Rice University Tutorial title: Constraint Satisfaction: An Introduction Abstract: A large class of problems in AI and other areas of computer science can be viewed as constraint-satisfaction problems. This includes problems in machine vision, belief maintenance, scheduling, temporal reasoning, type reconstruction, graph theory, and satisfiability. In general, the constraint satisfaction-problem is NP-complete, so searching for tractable cases is an active research area. It turns out that constraint satisfaction has an intimate connection with logic and database theory: constraint-satisfaction problems can be recast as logical and database problems and vice versa. In this tutorial, I will cover the fundamentals of constraints saisfaction and describe its intimate relationship with logic and database theory from various perspectives. Download part 1 of the slides of this talk here and part 2 here. Speaker: Ross Willard, University of Waterloo Tutorial title: Quick course in universal algebra and tame congruence theory Abstract: In this tutorial I will quickly explain the fundamentals of universal algebraic theory that are relevant to the algebraic approach to CSP (covered in A. Krokhin's tutorial). When analyzing finite algebras, one looks initially at their terms, congruences, and centrality (abelianness). More subtle information is discovered through the twin processes of localization and classification, which form the core of tame congruence theory and lead to the notion of the (Hobby-McKenzie) type-set of an algebra and of its generated variety. I will explain the elements of this theory, focussing on high-level understanding and illustrating with examples. Download the slides of this talk here. Speaker: László Zádori, University of Szeged, Hungary Title: Bounded width problems and algebras Abstract: In their seminal paper, Feder and Vardi introduced the class of bounded width problems. This class consists of certain tractable CSPs over a finite relational structure. In the talk I give an overview of the results on bounded width structures from an algebraic perspective. I touch upon some of the following topics: bounded width algorithms, definition of width, (l,k)-tree duality, bounded strict width (near unanimity), the width 1 case, examples of width 2 and of no bounded width, bounded width algebras and the Hobby-McKenzie types, related notions of width, progress in the congruence distributive case. Download the slides of this talk here. |