Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)
Peter Jonsson, Victor Lagerkvist, and George Osipov. CSPs with Few Alien Constraints. In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{jonsson_et_al:LIPIcs.CP.2024.15, author = {Jonsson, Peter and Lagerkvist, Victor and Osipov, George}, title = {{CSPs with Few Alien Constraints}}, booktitle = {30th International Conference on Principles and Practice of Constraint Programming (CP 2024)}, pages = {15:1--15:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-336-2}, ISSN = {1868-8969}, year = {2024}, volume = {307}, editor = {Shaw, Paul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.15}, URN = {urn:nbn:de:0030-drops-207005}, doi = {10.4230/LIPIcs.CP.2024.15}, annote = {Keywords: Constraint satisfaction, parameterized complexity, hybrid theories} }
Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Zeno Bitter and Antoine Mottet. Generalized Completion Problems with Forbidden Tournaments. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 28:1-28:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bitter_et_al:LIPIcs.MFCS.2024.28, author = {Bitter, Zeno and Mottet, Antoine}, title = {{Generalized Completion Problems with Forbidden Tournaments}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {28:1--28:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-335-5}, ISSN = {1868-8969}, year = {2024}, volume = {306}, editor = {Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.28}, URN = {urn:nbn:de:0030-drops-205844}, doi = {10.4230/LIPIcs.MFCS.2024.28}, annote = {Keywords: Tournaments, completion problems, constraint satisfaction problems, homogeneous structures, polymorphisms} }
Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Julien Grange, Fabian Vehlken, Nils Vortmeier, and Thomas Zeume. Specification and Automatic Verification of Computational Reductions. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 56:1-56:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{grange_et_al:LIPIcs.MFCS.2024.56, author = {Grange, Julien and Vehlken, Fabian and Vortmeier, Nils and Zeume, Thomas}, title = {{Specification and Automatic Verification of Computational Reductions}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {56:1--56:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-335-5}, ISSN = {1868-8969}, year = {2024}, volume = {306}, editor = {Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.56}, URN = {urn:nbn:de:0030-drops-206122}, doi = {10.4230/LIPIcs.MFCS.2024.56}, annote = {Keywords: Computational reductions, automatic verification, decidability} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Venkatesan Guruswami, Xuandi Ren, and Sai Sandeep. Baby PIH: Parameterized Inapproximability of Min CSP. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{guruswami_et_al:LIPIcs.CCC.2024.27, author = {Guruswami, Venkatesan and Ren, Xuandi and Sandeep, Sai}, title = {{Baby PIH: Parameterized Inapproximability of Min CSP}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {27:1--27:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.27}, URN = {urn:nbn:de:0030-drops-204237}, doi = {10.4230/LIPIcs.CCC.2024.27}, annote = {Keywords: Parameterized Inapproximability Hypothesis, Constraint Satisfaction Problems} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Alberto Larrauri and Stanislav Živný. Solving Promise Equations over Monoids and Groups. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 146:1-146:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{larrauri_et_al:LIPIcs.ICALP.2024.146, author = {Larrauri, Alberto and \v{Z}ivn\'{y}, Stanislav}, title = {{Solving Promise Equations over Monoids and Groups}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {146:1--146:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.146}, URN = {urn:nbn:de:0030-drops-202893}, doi = {10.4230/LIPIcs.ICALP.2024.146}, annote = {Keywords: constraint satisfaction, promise constraint satisfaction, equations, minions} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Antoine Mottet, Tomáš Nagy, and Michael Pinsker. An Order out of Nowhere: A New Algorithm for Infinite-Domain {CSP}s. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 148:1-148:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{mottet_et_al:LIPIcs.ICALP.2024.148, author = {Mottet, Antoine and Nagy, Tom\'{a}\v{s} and Pinsker, Michael}, title = {{An Order out of Nowhere: A New Algorithm for Infinite-Domain \{CSP\}s}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {148:1--148:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.148}, URN = {urn:nbn:de:0030-drops-202912}, doi = {10.4230/LIPIcs.ICALP.2024.148}, annote = {Keywords: Constraint Satisfaction Problems, Hypergraphs, Polymorphisms} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Jakub Rydval. Homogeneity and Homogenizability: Hard Problems for the Logic SNP. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 150:1-150:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{rydval:LIPIcs.ICALP.2024.150, author = {Rydval, Jakub}, title = {{Homogeneity and Homogenizability: Hard Problems for the Logic SNP}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {150:1--150:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.150}, URN = {urn:nbn:de:0030-drops-202939}, doi = {10.4230/LIPIcs.ICALP.2024.150}, annote = {Keywords: constraint satisfaction problems, finitely bounded, homogeneous, amalgamation property, universal, SNP, homogenizable} }
Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)
Kristina Asimi, Libor Barto, and Silvia Butti. Fixed-Template Promise Model Checking Problems. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 2:1-2:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{asimi_et_al:LIPIcs.CP.2022.2, author = {Asimi, Kristina and Barto, Libor and Butti, Silvia}, title = {{Fixed-Template Promise Model Checking Problems}}, booktitle = {28th International Conference on Principles and Practice of Constraint Programming (CP 2022)}, pages = {2:1--2:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-240-2}, ISSN = {1868-8969}, year = {2022}, volume = {235}, editor = {Solnon, Christine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.2}, URN = {urn:nbn:de:0030-drops-166310}, doi = {10.4230/LIPIcs.CP.2022.2}, annote = {Keywords: Model Checking Problem, First-Order Logic, Promise Constraint Satisfaction Problem, Multi-Homomorphism} }
Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)
Libor Barto and Silvia Butti. Weisfeiler-Leman Invariant Promise Valued CSPs. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{barto_et_al:LIPIcs.CP.2022.4, author = {Barto, Libor and Butti, Silvia}, title = {{Weisfeiler-Leman Invariant Promise Valued CSPs}}, booktitle = {28th International Conference on Principles and Practice of Constraint Programming (CP 2022)}, pages = {4:1--4:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-240-2}, ISSN = {1868-8969}, year = {2022}, volume = {235}, editor = {Solnon, Christine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.4}, URN = {urn:nbn:de:0030-drops-166332}, doi = {10.4230/LIPIcs.CP.2022.4}, annote = {Keywords: Promise Valued Constraint Satisfaction Problem, Linear programming relaxation, Distributed algorithms, Symmetric fractional polymorphisms, Color refinement algorithm} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Kristina Asimi and Libor Barto. Finitely Tractable Promise Constraint Satisfaction Problems. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{asimi_et_al:LIPIcs.MFCS.2021.11, author = {Asimi, Kristina and Barto, Libor}, title = {{Finitely Tractable Promise Constraint Satisfaction Problems}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {11:1--11:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-201-3}, ISSN = {1868-8969}, year = {2021}, volume = {202}, editor = {Bonchi, Filippo and Puglisi, Simon J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.11}, URN = {urn:nbn:de:0030-drops-144519}, doi = {10.4230/LIPIcs.MFCS.2021.11}, annote = {Keywords: Constraint satisfaction problems, promise constraint satisfaction, Boolean PCSP, polymorphism, finite tractability, homomorphic relaxation} }
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.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: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Libor Barto, Diego Battistelli, and Kevin M. Berg. Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{barto_et_al:LIPIcs.STACS.2021.10, author = {Barto, Libor and Battistelli, Diego and Berg, Kevin M.}, title = {{Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {10:1--10:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.10}, URN = {urn:nbn:de:0030-drops-136557}, doi = {10.4230/LIPIcs.STACS.2021.10}, annote = {Keywords: constraint satisfaction problems, promise constraint satisfaction, Boolean PCSP, polymorphism} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Libor Barto, Marcin Kozik, Johnson Tan, and Matt Valeriote. Sensitive Instances of the Constraint Satisfaction Problem. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 110:1-110:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{barto_et_al:LIPIcs.ICALP.2020.110, author = {Barto, Libor and Kozik, Marcin and Tan, Johnson and Valeriote, Matt}, title = {{Sensitive Instances of the Constraint Satisfaction Problem}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {110:1--110:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.110}, URN = {urn:nbn:de:0030-drops-125176}, doi = {10.4230/LIPIcs.ICALP.2020.110}, annote = {Keywords: Constraint satisfaction problem, bounded width, local consistency, near unanimity operation, loop lemma} }
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.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.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} }
Feedback for Dagstuhl Publishing