LZI - Schloss Dagstuhl - Talks + Materials of Seminar 12451
 Functions: 

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

 



License

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: