LZI - Schloss Dagstuhl - Talks + Materials of Seminar 12451

Seminar 12451
The Constraint Satisfaction Problem: Complexity and Approximability

Johan Hastad (KTH Stockholm, SE), Andrei Krokhin (University of Durham, GB), Dániel Marx (HU Berlin, DE)

Caveat: Due to caching problems of dynamic webpages, sometimes newly
uploaded files are not shown. Please reload the page accordingly.


Seminar Wide Materials

Albert Atserias , UPC - BarcelonaTech
 Semi-algebraic proofs, Gaussian elimination, and CSPs with short proofs of unsatisfiability
Abstracts: txt


Per Austrin , KTH Stockholm
 Approximability of Constraint Satisfaction Problems: A Tutorial
Abstracts: txt Slides: pdf


Libor Barto , Charles University - Prague
 Robust Satisfiability of Constraint Satisfaction Problems
Abstracts: txt Slides: pdf Paper: pdf


Manuel Bodirsky , Ecole Polytechnique - Palaiseau

Andrei A. Bulatov , Simon Fraser University - Burnaby
 Counting CSPs and Datalog fixed points
Abstracts: txt Slides: pdf


Catarina Carvalho , University of Hertfordshire

Hubie Chen , Universidad del País Vasco - Donostia
 Meditations on Quantified Constraint Satisfaction
Abstracts: txt Slides: pdf Other: pdf


David Cohen , Royal Holloway University of London

Victor Dalmau , UPF - Barcelona
 Robust approximability with polynomial loss.
Abstracts: txt Slides: pdf Paper: pdf


Martin Dyer , University of Leeds
 The complexity of approximating conservative counting CSPs
Abstracts: txt


Leslie Ann Goldberg , University of Liverpool
 Approximate Weighted Boolean #CSPs
Abstracts: txt


Martin Grohe , RWTH Aachen

Venkatesan Guruswami , Carnegie Mellon University - Pittsburgh

Gregory Z. Gutin , Royal Holloway University of London
 CSPs Parameterized Above Tight Lower Bounds
Abstracts: txt Slides: pdf


Johan Hastad , KTH Stockholm
 On the NP-hardness of Max-Not-2
Abstracts: txt Paper: pdf


Sangxia Huang , KTH - Stockholm
 Approximation Resistance on Satisfiable Instances for Predicates with few Accepting Assignments
Abstracts: txt Slides: pdf


Anna Huber , University of Durham
 VCSPs on Three Elements
Abstracts: txtpdf Slides: pdf Paper: pdf


Mark Jerrum , Queen Mary University of London
 Functional clones
Abstracts: txt Slides: pdf


Peter Jonsson , Linköping University
 Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis
Abstracts: txt Slides: pdf


Vladimir Kolmogorov , IST Austria - Klosterneuburg
 Linear Programming and VCSPs revisited
Abstracts: txt Slides: ppt


Marcin Kozik , Jagiellonian University - Kraków
 Some of the CSP's solvable in linear datalog
Abstracts: txt


Stefan Kratsch , TU Berlin

Andrei Krokhin , University of Durham
 A tutorial on Algebra and CSP, Part 1
Abstracts: txt Slides: pdf


Benoit Larose , Champlain Regional College - St. Lambert

Pin-Yan Lu , Microsoft Research Asia
 Holant Problems: CSPs where each variable appears exactly twice
Abstracts: txt Slides: pdf


Konstantin Makarychev , Microsoft Research - Redmond
 Local Search is Better than Random Assignment for Bounded Occurrence Ordering k-CSPs
Abstracts: txt


Yury Makarychev , Toyota Technological Institute - Chicago
 Approximation Algorithm for Non-Boolean MAX k-CSP
Abstracts: txt


Petar Markovic , University of Novi Sad
 On combinations of semilattice and Bulatov-Dalmau's algorithms
Abstracts: txt


Barnaby Martin , Middlesex University
 Constraint satisfaction with counting quantifiers
Abstracts: txt Slides: pdf


Daniel Marx , Hungarian Academy of Sciences
 CSPs and fixed-parameter tractability
Abstracts: txt Slides: pdf


Ralph McKenzie , Vanderbilt University - Nashville
 The dichotomy conjecture: sketching the algebraic landscape near the boundary
Abstracts: txtpdf


Michael Pinsker , University Paris-Diderot
 Topological Birkhoff
Abstracts: txt Slides: pdf Paper: pdf


Prasad Raghavendra , Georgia Institute of Technology
 Efficient algorithms via polymorphisms in value oracle model
Abstracts: txt

 Efficient Algorithms via polymorphisms in the value oracle model
Abstracts: pdf Slides: pptx


Francesco Scarcello , University of Calabria
 On the Desirability of Tree Projections: The Power of Local Consistency and Larger Islands of Tractability
Abstracts: txt Slides: pdf


Ola Svensson , EPFL - Lausanne
 Approximating k-Median via Pseudo-Approximation
Abstracts: txt


Stefan Szeider , TU Wien
 Structural Parameterizations of Language Restricted Constraint Satisfaction Problems
Abstracts: txt


Suguru Tamaki , Kyoto University
 A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis
Abstracts: txt


Johan Thapper , Ecole Polytechnique - Palaiseau
 The complexity of finite-valued CSPs
Abstracts: txt Slides: pdf


Matt Valeriote , McMaster University - Hamilton

Moshe Y. Vardi , Rice University
 Definability by Conjunctive Queries
Abstracts: txt

 Templates for Linear Datalog
Abstracts: txt


Magnus Wahlstroem , MPI für Informatik - Saarbrücken

Ross Willard , University of Waterloo
 A tutorial on algebra and CSP, Part 2
Abstracts: txt Slides: pdf


Yuichi Yoshida , National Institute of Informatics - Tokyo
 Testing Assignments of Boolean CSPs
Abstracts: txt Slides: pptx


Stanislav Zivny , University of Warwick
 Linear Programming and VCSPs
Abstracts: txt Slides: pdf



Creative Commons License
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: