Dagstuhl Follow-Ups, Volume 7
Editors: Andrei Krokhin and Stanislav Zivny
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Joshua Brakensiek, Venkatesan Guruswami, and Sai Sandeep. Conditional Dichotomy of Boolean Ordered Promise CSPs. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 37:1-37:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{brakensiek_et_al:LIPIcs.ICALP.2021.37, author = {Brakensiek, Joshua and Guruswami, Venkatesan and Sandeep, Sai}, title = {{Conditional Dichotomy of Boolean Ordered Promise CSPs}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {37:1--37:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.37}, URN = {urn:nbn:de:0030-drops-141060}, doi = {10.4230/LIPIcs.ICALP.2021.37}, annote = {Keywords: promise constraint satisfaction, Boolean ordered PCSP, Shapley value, rich 2-to-1 conjecture, random minor} }
Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)
The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@Collection{DFU.Vol7.15301, title = {{DFU, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability, Complete Volume}}, booktitle = {The Constraint Satisfaction Problem: Complexity and Approximability}, series = {Dagstuhl Follow-Ups}, ISBN = {978-3-95977-003-3}, ISSN = {1868-8977}, year = {2017}, volume = {7}, editor = {Krokhin, Andrei and Zivny, Stanislav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301}, URN = {urn:nbn:de:0030-drops-69752}, doi = {10.4230/DFU.Vol7.15301}, annote = {Keywords: Nonnumerical Algorithms and Problems} }
Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)
The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 0:i-0:xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InCollection{krokhin_et_al:DFU.Vol7.15301.i, author = {Krokhin, Andrei and Zivny, Stanislav}, title = {{Front Matter, Table of Contents, Preface, List of Authors}}, booktitle = {The Constraint Satisfaction Problem: Complexity and Approximability}, pages = {0:i--0:xii}, series = {Dagstuhl Follow-Ups}, ISBN = {978-3-95977-003-3}, ISSN = {1868-8977}, year = {2017}, volume = {7}, editor = {Krokhin, Andrei and Zivny, Stanislav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.i}, URN = {urn:nbn:de:0030-drops-69702}, doi = {10.4230/DFU.Vol7.15301.i}, annote = {Keywords: Front Matter, Table of Contents, Preface, List of Authors} }
Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)
Libor Barto, Andrei Krokhin, and Ross Willard. Polymorphisms, and How to Use Them. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 1-44, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InCollection{barto_et_al:DFU.Vol7.15301.1, author = {Barto, Libor and Krokhin, Andrei and Willard, Ross}, title = {{Polymorphisms, and How to Use Them}}, booktitle = {The Constraint Satisfaction Problem: Complexity and Approximability}, pages = {1--44}, series = {Dagstuhl Follow-Ups}, ISBN = {978-3-95977-003-3}, ISSN = {1868-8977}, year = {2017}, volume = {7}, editor = {Krokhin, Andrei and Zivny, Stanislav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.1}, URN = {urn:nbn:de:0030-drops-69595}, doi = {10.4230/DFU.Vol7.15301.1}, annote = {Keywords: Constraint satisfaction, Complexity, Universal algebra, Polymorphism} }
Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)
Libor Barto and Marcin Kozik. Absorption in Universal Algebra and CSP. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 45-77, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InCollection{barto_et_al:DFU.Vol7.15301.45, author = {Barto, Libor and Kozik, Marcin}, title = {{Absorption in Universal Algebra and CSP}}, booktitle = {The Constraint Satisfaction Problem: Complexity and Approximability}, pages = {45--77}, series = {Dagstuhl Follow-Ups}, ISBN = {978-3-95977-003-3}, ISSN = {1868-8977}, year = {2017}, volume = {7}, editor = {Krokhin, Andrei and Zivny, Stanislav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.45}, URN = {urn:nbn:de:0030-drops-69608}, doi = {10.4230/DFU.Vol7.15301.45}, annote = {Keywords: Constraint satisfaction problem, Algebraic approach, Absorption} }
Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)
Manuel Bodirsky and Marcello Mamino. Constraint Satisfaction Problems over Numeric Domains. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 79-111, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InCollection{bodirsky_et_al:DFU.Vol7.15301.79, author = {Bodirsky, Manuel and Mamino, Marcello}, title = {{Constraint Satisfaction Problems over Numeric Domains}}, booktitle = {The Constraint Satisfaction Problem: Complexity and Approximability}, pages = {79--111}, series = {Dagstuhl Follow-Ups}, ISBN = {978-3-95977-003-3}, ISSN = {1868-8977}, year = {2017}, volume = {7}, editor = {Krokhin, Andrei and Zivny, Stanislav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.79}, URN = {urn:nbn:de:0030-drops-69580}, doi = {10.4230/DFU.Vol7.15301.79}, annote = {Keywords: Constraint satisfaction problems, Numerical domains} }
Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)
Martin C. Cooper and Stanislav Zivny. Hybrid Tractable Classes of Constraint Problems. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 113-135, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InCollection{cooper_et_al:DFU.Vol7.15301.113, author = {Cooper, Martin C. and Zivny, Stanislav}, title = {{Hybrid Tractable Classes of Constraint Problems}}, booktitle = {The Constraint Satisfaction Problem: Complexity and Approximability}, pages = {113--135}, series = {Dagstuhl Follow-Ups}, ISBN = {978-3-95977-003-3}, ISSN = {1868-8977}, year = {2017}, volume = {7}, editor = {Krokhin, Andrei and Zivny, Stanislav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.113}, URN = {urn:nbn:de:0030-drops-69616}, doi = {10.4230/DFU.Vol7.15301.113}, annote = {Keywords: Constraint satisfaction problems, Optimisation, Tractability} }
Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)
Serge Gaspers, Sebastian Ordyniak, and Stefan Szeider. Backdoor Sets for CSP. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 137-157, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InCollection{gaspers_et_al:DFU.Vol7.15301.137, author = {Gaspers, Serge and Ordyniak, Sebastian and Szeider, Stefan}, title = {{Backdoor Sets for CSP}}, booktitle = {The Constraint Satisfaction Problem: Complexity and Approximability}, pages = {137--157}, series = {Dagstuhl Follow-Ups}, ISBN = {978-3-95977-003-3}, ISSN = {1868-8977}, year = {2017}, volume = {7}, editor = {Krokhin, Andrei and Zivny, Stanislav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.137}, URN = {urn:nbn:de:0030-drops-69626}, doi = {10.4230/DFU.Vol7.15301.137}, annote = {Keywords: Backdoor sets, Constraint satisfaction problems, Parameterized complexity, Polymorphisms} }
Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)
Heng Guo and Pinyan Lu. On the Complexity of Holant Problems. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 159-177, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InCollection{guo_et_al:DFU.Vol7.15301.159, author = {Guo, Heng and Lu, Pinyan}, title = {{On the Complexity of Holant Problems}}, booktitle = {The Constraint Satisfaction Problem: Complexity and Approximability}, pages = {159--177}, series = {Dagstuhl Follow-Ups}, ISBN = {978-3-95977-003-3}, ISSN = {1868-8977}, year = {2017}, volume = {7}, editor = {Krokhin, Andrei and Zivny, Stanislav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.159}, URN = {urn:nbn:de:0030-drops-69630}, doi = {10.4230/DFU.Vol7.15301.159}, annote = {Keywords: Computational complexity, Counting complexity, Dichotomy theorems, Approximate counting, Holant problems} }
Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)
Gregory Gutin and Anders Yeo. Parameterized Constraint Satisfaction Problems: a Survey. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 179-203, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InCollection{gutin_et_al:DFU.Vol7.15301.179, author = {Gutin, Gregory and Yeo, Anders}, title = {{Parameterized Constraint Satisfaction Problems: a Survey}}, booktitle = {The Constraint Satisfaction Problem: Complexity and Approximability}, pages = {179--203}, series = {Dagstuhl Follow-Ups}, ISBN = {978-3-95977-003-3}, ISSN = {1868-8977}, year = {2017}, volume = {7}, editor = {Krokhin, Andrei and Zivny, Stanislav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.179}, URN = {urn:nbn:de:0030-drops-69641}, doi = {10.4230/DFU.Vol7.15301.179}, annote = {Keywords: Constraint satisfaction problems, Fixed-parameter tractability} }
Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)
Mark Jerrum. Counting Constraint Satisfaction Problems. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 205-231, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InCollection{jerrum:DFU.Vol7.15301.205, author = {Jerrum, Mark}, title = {{Counting Constraint Satisfaction Problems}}, booktitle = {The Constraint Satisfaction Problem: Complexity and Approximability}, pages = {205--231}, series = {Dagstuhl Follow-Ups}, ISBN = {978-3-95977-003-3}, ISSN = {1868-8977}, year = {2017}, volume = {7}, editor = {Krokhin, Andrei and Zivny, Stanislav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.205}, URN = {urn:nbn:de:0030-drops-69655}, doi = {10.4230/DFU.Vol7.15301.205}, annote = {Keywords: Approximation algorithms, Computational complexity, Constraint satisfaction problems, Counting problems, Partition functions} }
Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)
Andrei Krokhin and Stanislav Zivny. The Complexity of Valued CSPs. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 233-266, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InCollection{krokhin_et_al:DFU.Vol7.15301.233, author = {Krokhin, Andrei and Zivny, Stanislav}, title = {{The Complexity of Valued CSPs}}, booktitle = {The Constraint Satisfaction Problem: Complexity and Approximability}, pages = {233--266}, series = {Dagstuhl Follow-Ups}, ISBN = {978-3-95977-003-3}, ISSN = {1868-8977}, year = {2017}, volume = {7}, editor = {Krokhin, Andrei and Zivny, Stanislav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.233}, URN = {urn:nbn:de:0030-drops-69665}, doi = {10.4230/DFU.Vol7.15301.233}, annote = {Keywords: Constraint satisfaction problems, Optimisation, Tractability} }
Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)
Benoit Larose. Algebra and the Complexity of Digraph CSPs: a Survey. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 267-285, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InCollection{larose:DFU.Vol7.15301.267, author = {Larose, Benoit}, title = {{Algebra and the Complexity of Digraph CSPs: a Survey}}, booktitle = {The Constraint Satisfaction Problem: Complexity and Approximability}, pages = {267--285}, series = {Dagstuhl Follow-Ups}, ISBN = {978-3-95977-003-3}, ISSN = {1868-8977}, year = {2017}, volume = {7}, editor = {Krokhin, Andrei and Zivny, Stanislav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.267}, URN = {urn:nbn:de:0030-drops-69677}, doi = {10.4230/DFU.Vol7.15301.267}, annote = {Keywords: Constraint satisfaction problems, Polymorphisms, Digraphs} }
Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)
Konstantin Makarychev and Yury Makarychev. Approximation Algorithms for CSPs. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 287-325, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InCollection{makarychev_et_al:DFU.Vol7.15301.287, author = {Makarychev, Konstantin and Makarychev, Yury}, title = {{Approximation Algorithms for CSPs}}, booktitle = {The Constraint Satisfaction Problem: Complexity and Approximability}, pages = {287--325}, series = {Dagstuhl Follow-Ups}, ISBN = {978-3-95977-003-3}, ISSN = {1868-8977}, year = {2017}, volume = {7}, editor = {Krokhin, Andrei and Zivny, Stanislav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.287}, URN = {urn:nbn:de:0030-drops-69685}, doi = {10.4230/DFU.Vol7.15301.287}, annote = {Keywords: Constraint satisfaction problems, Approximation algorithms, SDP, UGC} }
Feedback for Dagstuhl Publishing