LZI - Schloss Dagstuhl - Talks + Materials of Seminar 06401

Collector buttons:

Seminar 06401
Complexity of Constraints

N. Creignou (Univ. de Marseille, FR), Ph. Kolaitis (Univ. California - Santa Cruz, US), H. Vollmer (Univ. Hannover, DE)

Seminar Wide Materials

Complexity of Constraints - Schedule of Talks

Abstracts:

Other:

Complexity of Constraints - Summary

Abstracts:

DROPS-Submission:

	Upload or overwrite a document file and/or change title of talk


	Due to caching problems of microsofts internet explorer concerning dynamic webpages, sometimes newly uploaded files are not shown. By pressing [CTRL]+[F5], the page is completely reloaded.

Albert Atserias , TU of Catalonia - Barcelona

On the power of k-consistency

Abstracts:

Slides:

Régis Barbanchon , Université de la Méditerrannée - Marseille

Michael Bauland , Universität Hannover

Manuel Bodirsky , HU Berlin

Complexity of Temporal Constraint Satisfaction

Abstracts:

Slides:

Andrei A. Bulatov , Simon Fraser University

CSP, algebras, and varieties

Abstracts:

Slides:

Elmar Böhler , Universität Würzburg

Ferdinand Börner , Universität Potsdam

Basic Universal Algebra

Abstracts:

Slides:

Some other Galois connections

Abstracts:

Slides:

Catarina Carvalho , University of Durham

Philippe Chapdelaine , IUT Sénart-Fontainebleau

Hubie Chen , Univ. Pompeu Fabra - Barcelona

Quantified equality constraints

Abstracts:

David Cohen , RHUL - London

Expressibility of VCSPs

Abstracts:

Slides:

A Unifying Theory of Structural Decompostions for the CSP problem

Abstracts:

Slides:

DROPS-Submission:

Nadia Creignou , Université de Marseille

Victor Dalmau , Univ. Pompeu Fabra - Barcelona

Anuj Dawar , Cambridge University

Definability of CSPs in Fixed-point logics

Abstracts:

Slides:

Arnaud Durand , Université Paris VII

Enumeration Complexity of Query Problems and Quantifier Elimination

Abstracts:

Slides:

Martin Grohe , HU Berlin

Constraint Satisfaction with Succinctly Specified Relations

Abstracts:

Slides:

DROPS-Submission:

Marc Gyssens , Hasselt University

A short overview of hinges

Abstracts:

Slides:

Miki Hermann , Ecole Polytechnique - Palaiseau

Complexity of Clausal Constraints Over Chains

Abstracts:

Slides:

Neil Immerman , Univ. of Massachusetts - Amherst

Dmitry Itsykson , Steklov Inst. - St. Petersburg

Exponential Lower Bound for tree-like Lovasz-Schrijver proof systems

Abstracts:

Slides:

Peter Jonsson , Linköping University

Lefteris M. Kirousis , CTI & University of Patras

Random Constraint Optimization: The Case of Max-Cut

Abstracts:

Slides:

Paper:

Phokion Kolaitis , IBM Almaden Center & UC Santa Cruz

Andrei Krokhin , University of Durham

Constraint satisfaction problems and dualities

Abstracts:

Slides:

Oliver Kullmann , University of Wales - Swansea

CSPs in clausal form: Autarkies, minimal unsatisfiability, hypergraphs

Abstracts:

Slides:

DROPS-Submission:

Practical SAT algorithms

Abstracts:

Slides:

Other:

Benoit Larose , Champlain Regional College - St. Lambert

Non FO CSP's are Logspace hard

Abstracts:

Slides:

Florent R. Madelaine , University of Durham

Constraint satisfaction, structure homomorphisms and fragments of second order logic.

Abstracts:

Slides:

Elitza Maneva , Univ. California - Berkeley

Connectivity of Boolean Satisfiability: Structural and Computational Dichotomies

Abstracts:

Slides:

A New Look at Survey Propagation

Abstracts:

Slides:

Joachim Niehren , INRIA Futurs - Lille

On XPath Dialects with Variables

Abstracts:

Slides:

Gustav Nordh , Linköping University

Complexity of Maximum Solution: Max-Ones Generalised to Larger Domains

Abstracts:

Slides:

Steffen Reith , Fachhochschule Wiesbaden

Florian Richoux , Ecole Polytechnique - Palaiseau

Francesco Scarcello , University of Calabria

Islands of Tractability for Uniform CSP, and their Relationship to Database Theory

Abstracts:

Slides:

Henning Schnoor , Universität Hannover

Efficient Enumeration Algorithms for Constraint Satisfaction Problems

Abstracts:

Slides:

DROPS-Submission:

Ilka Schnoor , Universität Hannover

Partial clones and Constraint Satisfaction

Abstracts:

Slides:

DROPS-Submission:

Iain A. Stewart , University of Durham

Stefan Szeider , University of Durham

Fixed-parameter tractable constraint satisfaction

Abstracts:

Slides:

Pascal Tesson , Laval University - Quebec

Systems of equations over finite semigroups and the #CSP dichotomy

Abstracts:

Slides:

Matt Valeriote , McMaster University

Advanced Universal Algebra and the CSP

Abstracts:

Slides:

Heribert Vollmer , Universität Hannover

Boolean Constraint Satisfaction Problems

Abstracts:

Slides:

Copyright

This webpage and the material that is made available on this webpage is licensed under a
Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 Unported License.

The CC by-nc-nd license allows you to copy, distribute and transmit the work under the following conditions:

Attribution: You must attribute the work in the manner specified by the author or licensor (but not in any way that suggests that they endorse you or your use of the work).
Noncommercial: You may not use this work for commercial purposes.
No Derivative Works: You may not alter, transform, or build upon this work.

Seminar 06401 Complexity of Constraints

Copyright

Seminar 06401
Complexity of Constraints