Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Nadia Creignou, Arnaud Durand, and Heribert Vollmer. Enumeration Classes Defined by Circuits. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 38:1-38:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{creignou_et_al:LIPIcs.MFCS.2022.38, author = {Creignou, Nadia and Durand, Arnaud and Vollmer, Heribert}, title = {{Enumeration Classes Defined by Circuits}}, booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)}, pages = {38:1--38:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-256-3}, ISSN = {1868-8969}, year = {2022}, volume = {241}, editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.38}, URN = {urn:nbn:de:0030-drops-168364}, doi = {10.4230/LIPIcs.MFCS.2022.38}, annote = {Keywords: Computational complexity, enumeration problem, Boolean circuit} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Andrei A. Bulatov and Stanislav Živný. Approximate Counting CSP Seen from the Other Side. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 60:1-60:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bulatov_et_al:LIPIcs.MFCS.2019.60, author = {Bulatov, Andrei A. and \v{Z}ivn\'{y}, Stanislav}, title = {{Approximate Counting CSP Seen from the Other Side}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {60:1--60:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.60}, URN = {urn:nbn:de:0030-drops-110041}, doi = {10.4230/LIPIcs.MFCS.2019.60}, annote = {Keywords: constraint satisfaction, approximate counting, homomorphisms} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Karl Bringmann, Nick Fischer, and Marvin Künnemann. A Fine-Grained Analogue of Schaefer’s Theorem in P: Dichotomy of Exists^k-Forall-Quantified First-Order Graph Properties. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 31:1-31:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bringmann_et_al:LIPIcs.CCC.2019.31, author = {Bringmann, Karl and Fischer, Nick and K\"{u}nnemann, Marvin}, title = {{A Fine-Grained Analogue of Schaefer’s Theorem in P: Dichotomy of Exists^k-Forall-Quantified First-Order Graph Properties}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {31:1--31:27}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.31}, URN = {urn:nbn:de:0030-drops-108533}, doi = {10.4230/LIPIcs.CCC.2019.31}, annote = {Keywords: Fine-grained Complexity, Hardness in P, Hyperclique Conjecture, Constrained Triangle Detection} }
Published in: Dagstuhl Reports, Volume 6, Issue 9 (2017)
Olaf Beyersdorff, Nadia Creignou, Uwe Egly, and Heribert Vollmer. SAT and Interactions (Dagstuhl Seminar 16381). In Dagstuhl Reports, Volume 6, Issue 9, pp. 74-93, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@Article{beyersdorff_et_al:DagRep.6.9.74, author = {Beyersdorff, Olaf and Creignou, Nadia and Egly, Uwe and Vollmer, Heribert}, title = {{SAT and Interactions (Dagstuhl Seminar 16381)}}, pages = {74--93}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2017}, volume = {6}, number = {9}, editor = {Beyersdorff, Olaf and Creignou, Nadia and Egly, Uwe and Vollmer, Heribert}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.6.9.74}, URN = {urn:nbn:de:0030-drops-69116}, doi = {10.4230/DagRep.6.9.74}, annote = {Keywords: Combinatorics, Computational Complexity, P vs. NP, Proof Complexity, Quantified Boolean formulas, SAT-solvers, satisfiability problem} }
Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)
Holger Dell, Eun Jung Kim, Michael Lampis, Valia Mitsou, and Tobias Mömke. Complexity and Approximability of Parameterized MAX-CSPs. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 294-306, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{dell_et_al:LIPIcs.IPEC.2015.294, author = {Dell, Holger and Kim, Eun Jung and Lampis, Michael and Mitsou, Valia and M\"{o}mke, Tobias}, title = {{Complexity and Approximability of Parameterized MAX-CSPs}}, booktitle = {10th International Symposium on Parameterized and Exact Computation (IPEC 2015)}, pages = {294--306}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-92-7}, ISSN = {1868-8969}, year = {2015}, volume = {43}, editor = {Husfeldt, Thore and Kanj, Iyad}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.294}, URN = {urn:nbn:de:0030-drops-55910}, doi = {10.4230/LIPIcs.IPEC.2015.294}, annote = {Keywords: Approximation, Structural Parameters, Constraint Satisfaction} }
Published in: LIPIcs, Volume 31, 18th International Conference on Database Theory (ICDT 2015)
Balder ten Cate and Victor Dalmau. The Product Homomorphism Problem and Applications. In 18th International Conference on Database Theory (ICDT 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 31, pp. 161-176, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{tencate_et_al:LIPIcs.ICDT.2015.161, author = {ten Cate, Balder and Dalmau, Victor}, title = {{The Product Homomorphism Problem and Applications}}, booktitle = {18th International Conference on Database Theory (ICDT 2015)}, pages = {161--176}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-79-8}, ISSN = {1868-8969}, year = {2015}, volume = {31}, editor = {Arenas, Marcelo and Ugarte, Mart{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2015.161}, URN = {urn:nbn:de:0030-drops-49832}, doi = {10.4230/LIPIcs.ICDT.2015.161}, annote = {Keywords: Homomorphisms, Direct Product, Data Examples, Definability, Conjunctive Queries, Schema Mappings} }
Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Suguru Tamaki and Yuichi Yoshida. Robust Approximation of Temporal CSP. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 419-432, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{tamaki_et_al:LIPIcs.APPROX-RANDOM.2014.419, author = {Tamaki, Suguru and Yoshida, Yuichi}, title = {{Robust Approximation of Temporal CSP}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)}, pages = {419--432}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-74-3}, ISSN = {1868-8969}, year = {2014}, volume = {28}, editor = {Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.419}, URN = {urn:nbn:de:0030-drops-47135}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2014.419}, annote = {Keywords: constraint satisfaction, maximum satisfiability, approximation algorithm, hardness of approximation, infinite domain} }
Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Shlomo Jozeph. Universal Factor Graphs for Every NP-Hard Boolean CSP. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 274-283, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{jozeph:LIPIcs.APPROX-RANDOM.2014.274, author = {Jozeph, Shlomo}, title = {{Universal Factor Graphs for Every NP-Hard Boolean CSP}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)}, pages = {274--283}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-74-3}, ISSN = {1868-8969}, year = {2014}, volume = {28}, editor = {Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.274}, URN = {urn:nbn:de:0030-drops-47021}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2014.274}, annote = {Keywords: Hardness of Approximation, Hardness with Preprocessing} }
Published in: Dagstuhl Reports, Volume 2, Issue 11 (2013)
Nadia Creignou, Nicola Galesi, Oliver Kullmann, and Heribert Vollmer. SAT Interactions (Dagstuhl Seminar 12471). In Dagstuhl Reports, Volume 2, Issue 11, pp. 87-101, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2013)
@Article{creignou_et_al:DagRep.2.11.87, author = {Creignou, Nadia and Galesi, Nicola and Kullmann, Oliver and Vollmer, Heribert}, title = {{SAT Interactions (Dagstuhl Seminar 12471)}}, pages = {87--101}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2013}, volume = {2}, number = {11}, editor = {Creignou, Nadia and Galesi, Nicola and Kullmann, Oliver and Vollmer, Heribert}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.2.11.87}, URN = {urn:nbn:de:0030-drops-39786}, doi = {10.4230/DagRep.2.11.87}, annote = {Keywords: satisfiability problem, computational complexity, P-NP question, proof complexity, combinatorics, SAT-solvers, quantified Boolean formulas} }
Published in: Dagstuhl Seminar Proceedings, Volume 10061, Circuits, Logic, and Games (2010)
Nadia Creignou, Arne Meier, Michael Thomas, and Heribert Vollmer. The Complexity of Reasoning for Fragments of Autoepistemic Logic. In Circuits, Logic, and Games. Dagstuhl Seminar Proceedings, Volume 10061, pp. 1-10, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)
@InProceedings{creignou_et_al:DagSemProc.10061.6, author = {Creignou, Nadia and Meier, Arne and Thomas, Michael and Vollmer, Heribert}, title = {{The Complexity of Reasoning for Fragments of Autoepistemic Logic}}, booktitle = {Circuits, Logic, and Games}, pages = {1--10}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {10061}, editor = {Benjamin Rossman and Thomas Schwentick and Denis Th\'{e}rien and Heribert Vollmer}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10061.6}, URN = {urn:nbn:de:0030-drops-25234}, doi = {10.4230/DagSemProc.10061.6}, annote = {Keywords: Autoepistemic logic, computational complexity, nonmonotonic reasoning, Post's lattice} }
Published in: Dagstuhl Seminar Proceedings, Volume 6401, Complexity of Constraints (2006)
Nadia Creignou, Phokion Kolaitis, and Heribert Vollmer. 06401 Abstracts Collection – Complexity of Constraints. In Complexity of Constraints. Dagstuhl Seminar Proceedings, Volume 6401, pp. 1-14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2006)
@InProceedings{creignou_et_al:DagSemProc.06401.1, author = {Creignou, Nadia and Kolaitis, Phokion and Vollmer, Heribert}, title = {{06401 Abstracts Collection – Complexity of Constraints}}, booktitle = {Complexity of Constraints}, pages = {1--14}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2006}, volume = {6401}, editor = {Nadia Creignou and Phokion Kolaitis and Heribert Vollmer}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06401.1}, URN = {urn:nbn:de:0030-drops-8067}, doi = {10.4230/DagSemProc.06401.1}, annote = {Keywords: Constraint satisfaction problems, computational complexity, universal algebra, mathematical logic, finite model theory} }
Published in: Dagstuhl Seminar Proceedings, Volume 6401, Complexity of Constraints (2006)
Nadia Creignou, Phokion Kolaitis, and Heribert Vollmer. 06401 Executive Summary – Complexity of Constraints. In Complexity of Constraints. Dagstuhl Seminar Proceedings, Volume 6401, pp. 1-6, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2006)
@InProceedings{creignou_et_al:DagSemProc.06401.2, author = {Creignou, Nadia and Kolaitis, Phokion and Vollmer, Heribert}, title = {{06401 Executive Summary – Complexity of Constraints}}, booktitle = {Complexity of Constraints}, pages = {1--6}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2006}, volume = {6401}, editor = {Nadia Creignou and Phokion Kolaitis and Heribert Vollmer}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06401.2}, URN = {urn:nbn:de:0030-drops-8001}, doi = {10.4230/DagSemProc.06401.2}, annote = {Keywords: Constraint satisfaction problems, complexity} }
Published in: Dagstuhl Seminar Proceedings, Volume 6401, Complexity of Constraints (2006)
David Cohen, Marc Gyssens, and Peter Jeavons. A Unifying Theory of Structural Decompostions for the Constraint Satisfaction Problems. In Complexity of Constraints. Dagstuhl Seminar Proceedings, Volume 6401, pp. 1-22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2006)
@InProceedings{cohen_et_al:DagSemProc.06401.3, author = {Cohen, David and Gyssens, Marc and Jeavons, Peter}, title = {{A Unifying Theory of Structural Decompostions for the Constraint Satisfaction Problems}}, booktitle = {Complexity of Constraints}, pages = {1--22}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2006}, volume = {6401}, editor = {Nadia Creignou and Phokion Kolaitis and Heribert Vollmer}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06401.3}, URN = {urn:nbn:de:0030-drops-8017}, doi = {10.4230/DagSemProc.06401.3}, annote = {Keywords: Structural decomposition, spread cut} }
Published in: Dagstuhl Seminar Proceedings, Volume 6401, Complexity of Constraints (2006)
Oliver Kullmann. Constraint satisfaction problems in clausal form: Autarkies, minimal unsatisfiability, and applications to hypergraph inequalities. In Complexity of Constraints. Dagstuhl Seminar Proceedings, Volume 6401, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2006)
@InProceedings{kullmann:DagSemProc.06401.4, author = {Kullmann, Oliver}, title = {{Constraint satisfaction problems in clausal form: Autarkies, minimal unsatisfiability, and applications to hypergraph inequalities}}, booktitle = {Complexity of Constraints}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2006}, volume = {6401}, editor = {Nadia Creignou and Phokion Kolaitis and Heribert Vollmer}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06401.4}, URN = {urn:nbn:de:0030-drops-8030}, doi = {10.4230/DagSemProc.06401.4}, annote = {Keywords: Signed CNF, autarkies, minimal unsatisfiable, hypergraph colouring, block designs} }
Published in: Dagstuhl Seminar Proceedings, Volume 6401, Complexity of Constraints (2006)
Hubie Chen and Martin Grohe. Constraint Satisfaction with Succinctly Specified Relations. In Complexity of Constraints. Dagstuhl Seminar Proceedings, Volume 6401, pp. 1-15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2006)
@InProceedings{chen_et_al:DagSemProc.06401.5, author = {Chen, Hubie and Grohe, Martin}, title = {{Constraint Satisfaction with Succinctly Specified Relations}}, booktitle = {Complexity of Constraints}, pages = {1--15}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2006}, volume = {6401}, editor = {Nadia Creignou and Phokion Kolaitis and Heribert Vollmer}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06401.5}, URN = {urn:nbn:de:0030-drops-8022}, doi = {10.4230/DagSemProc.06401.5}, annote = {Keywords: Constraint satisfaction, complexity, succinct representations} }
Feedback for Dagstuhl Publishing