Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Martin Grohe, Gaurav Rattan, and Tim Seppelt. Homomorphism Tensors and Linear Equations. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 70:1-70:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{grohe_et_al:LIPIcs.ICALP.2022.70, author = {Grohe, Martin and Rattan, Gaurav and Seppelt, Tim}, title = {{Homomorphism Tensors and Linear Equations}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {70:1--70:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.70}, URN = {urn:nbn:de:0030-drops-164113}, doi = {10.4230/LIPIcs.ICALP.2022.70}, annote = {Keywords: homomorphisms, labelled graphs, treewidth, pathwidth, treedepth, linear equations, Sherali-Adams relaxation, Wiegmann-Specht Theorem, Weisfeiler-Leman} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Andrei A. Bulatov and Akbar Rafiey. The Ideal Membership Problem and Abelian Groups. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 18:1-18:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{bulatov_et_al:LIPIcs.STACS.2022.18, author = {Bulatov, Andrei A. and Rafiey, Akbar}, title = {{The Ideal Membership Problem and Abelian Groups}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {18:1--18:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra 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.2022.18}, URN = {urn:nbn:de:0030-drops-158280}, doi = {10.4230/LIPIcs.STACS.2022.18}, annote = {Keywords: Polynomial Ideal Membership, Constraint Satisfaction Problems, Polymorphisms, Gr\"{o}bner Bases, Abelian Groups} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Arpitha P. Bharathi and Monaldo Mastrolilli. Ideal Membership Problem for Boolean Minority and Dual Discriminator. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 16:1-16:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{bharathi_et_al:LIPIcs.MFCS.2021.16, author = {Bharathi, Arpitha P. and Mastrolilli, Monaldo}, title = {{Ideal Membership Problem for Boolean Minority and Dual Discriminator}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {16:1--16:20}, 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.16}, URN = {urn:nbn:de:0030-drops-144560}, doi = {10.4230/LIPIcs.MFCS.2021.16}, annote = {Keywords: Polynomial ideal membership, Polymorphisms, Gr\"{o}bner basis theory, Constraint satisfaction problems} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Andrei A. Bulatov. Symmetries and Complexity (Invited Talk). In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 2:1-2:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{bulatov:LIPIcs.ICALP.2021.2, author = {Bulatov, Andrei A.}, title = {{Symmetries and Complexity}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {2:1--2:17}, 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.2}, URN = {urn:nbn:de:0030-drops-140717}, doi = {10.4230/LIPIcs.ICALP.2021.2}, annote = {Keywords: constraint problems, algebraic approach, dichotomy theorems} }
Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Arpitha P. Bharathi and Monaldo Mastrolilli. Ideal Membership Problem and a Majority Polymorphism over the Ternary Domain. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 13:1-13:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{bharathi_et_al:LIPIcs.MFCS.2020.13, author = {Bharathi, Arpitha P. and Mastrolilli, Monaldo}, title = {{Ideal Membership Problem and a Majority Polymorphism over the Ternary Domain}}, booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)}, pages = {13:1--13:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-159-7}, ISSN = {1868-8969}, year = {2020}, volume = {170}, editor = {Esparza, Javier and Kr\'{a}l', Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.13}, URN = {urn:nbn:de:0030-drops-126829}, doi = {10.4230/LIPIcs.MFCS.2020.13}, annote = {Keywords: Polynomial ideal membership, Polymorphisms, Gr\"{o}bner basis theory, Constraint satisfaction problems} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Andrei A. Bulatov and Amineh Dadsetan. Counting Homomorphisms in Plain Exponential Time. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 21:1-21:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{bulatov_et_al:LIPIcs.ICALP.2020.21, author = {Bulatov, Andrei A. and Dadsetan, Amineh}, title = {{Counting Homomorphisms in Plain Exponential Time}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {21:1--21: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.21}, URN = {urn:nbn:de:0030-drops-124287}, doi = {10.4230/LIPIcs.ICALP.2020.21}, annote = {Keywords: graph homomorphisms, plain exponential time, clique width} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Artem Govorov, Jin-Yi Cai, and Martin Dyer. A Dichotomy for Bounded Degree Graph Homomorphisms with Nonnegative Weights. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 66:1-66:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{govorov_et_al:LIPIcs.ICALP.2020.66, author = {Govorov, Artem and Cai, Jin-Yi and Dyer, Martin}, title = {{A Dichotomy for Bounded Degree Graph Homomorphisms with Nonnegative Weights}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {66:1--66: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.66}, URN = {urn:nbn:de:0030-drops-124733}, doi = {10.4230/LIPIcs.ICALP.2020.66}, annote = {Keywords: Graph homomorphism, Complexity dichotomy, Counting problems} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Victor Lagerkvist and Gustav Nordh. On the Strength of Uniqueness Quantification in Primitive Positive Formulas. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 36:1-36:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{lagerkvist_et_al:LIPIcs.MFCS.2019.36, author = {Lagerkvist, Victor and Nordh, Gustav}, title = {{On the Strength of Uniqueness Quantification in Primitive Positive Formulas}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {36:1--36:15}, 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.36}, URN = {urn:nbn:de:0030-drops-109808}, doi = {10.4230/LIPIcs.MFCS.2019.36}, annote = {Keywords: Primitive positive definitions, clone theory, constraint satisfaction problems} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Amirhossein Kazeminia and Andrei A. Bulatov. Counting Homomorphisms Modulo a Prime Number. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 59:1-59:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{kazeminia_et_al:LIPIcs.MFCS.2019.59, author = {Kazeminia, Amirhossein and Bulatov, Andrei A.}, title = {{Counting Homomorphisms Modulo a Prime Number}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {59:1--59:13}, 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.59}, URN = {urn:nbn:de:0030-drops-110032}, doi = {10.4230/LIPIcs.MFCS.2019.59}, annote = {Keywords: graph homomorphism, modular counting, computational hardness} }
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 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Raimundo Briceño, Andrei A. Bulatov, Víctor Dalmau, and Benoît Larose. Dismantlability, Connectedness, and Mixing in Relational Structures. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 29:1-29:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{briceno_et_al:LIPIcs.ICALP.2019.29, author = {Brice\~{n}o, Raimundo and Bulatov, Andrei A. and Dalmau, V{\'\i}ctor and Larose, Beno\^{i}t}, title = {{Dismantlability, Connectedness, and Mixing in Relational Structures}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {29:1--29:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.29}, URN = {urn:nbn:de:0030-drops-106059}, doi = {10.4230/LIPIcs.ICALP.2019.29}, annote = {Keywords: relational structure, constraint satisfaction problem, homomorphism, mixing properties, Gibbs measure} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Akbar Rafiey, Arash Rafiey, and Thiago Santos. Toward a Dichotomy for Approximation of H-Coloring. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 91:1-91:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{rafiey_et_al:LIPIcs.ICALP.2019.91, author = {Rafiey, Akbar and Rafiey, Arash and Santos, Thiago}, title = {{Toward a Dichotomy for Approximation of H-Coloring}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {91:1--91:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.91}, URN = {urn:nbn:de:0030-drops-106678}, doi = {10.4230/LIPIcs.ICALP.2019.91}, annote = {Keywords: Approximation algorithms, minimum cost homomorphism, randomized rounding} }
Published in: Dagstuhl Reports, Volume 5, Issue 7 (2016)
Andrei A. Bulatov, Venkatesan Guruswami, Andrei Krokhin, and Dániel Marx. The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 15301). In Dagstuhl Reports, Volume 5, Issue 7, pp. 22-41, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@Article{bulatov_et_al:DagRep.5.7.22, author = {Bulatov, Andrei A. and Guruswami, Venkatesan and Krokhin, Andrei and Marx, D\'{a}niel}, title = {{The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 15301)}}, pages = {22--41}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2016}, volume = {5}, number = {7}, editor = {Bulatov, Andrei A. and Guruswami, Venkatesan and Krokhin, Andrei and Marx, D\'{a}niel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.5.7.22}, URN = {urn:nbn:de:0030-drops-56714}, doi = {10.4230/DagRep.5.7.22}, annote = {Keywords: Constraint satisfaction problem (CSP), Computational complexity, CSP dichotomy conjecture, Hardness of approximation, Unique games conjecture, Fixed-parameter tractability, Descriptive complexity, Universal algebra, Logic, Decomposition methods} }
Published in: LIPIcs, Volume 23, Computer Science Logic 2013 (CSL 2013)
Andrei Bulatov, Victor Dalmau, and Marc Thurley. Descriptive complexity of approximate counting CSPs. In Computer Science Logic 2013 (CSL 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 23, pp. 149-164, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2013)
@InProceedings{bulatov_et_al:LIPIcs.CSL.2013.149, author = {Bulatov, Andrei and Dalmau, Victor and Thurley, Marc}, title = {{Descriptive complexity of approximate counting CSPs}}, booktitle = {Computer Science Logic 2013 (CSL 2013)}, pages = {149--164}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-60-6}, ISSN = {1868-8969}, year = {2013}, volume = {23}, editor = {Ronchi Della Rocca, Simona}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2013.149}, URN = {urn:nbn:de:0030-drops-41955}, doi = {10.4230/LIPIcs.CSL.2013.149}, annote = {Keywords: Constraint Satisfaction Problems, Approximate Counting, Descriptive Complexity} }
Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Andrei A. Bulatov, Martin Dyer, Leslie Ann Goldberg, and Mark Jerrum. Log-supermodular functions, functional clones and counting CSPs. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 302-313, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2012)
@InProceedings{bulatov_et_al:LIPIcs.STACS.2012.302, author = {Bulatov, Andrei A. and Dyer, Martin and Goldberg, Leslie Ann and Jerrum, Mark}, title = {{Log-supermodular functions, functional clones and counting CSPs}}, booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)}, pages = {302--313}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-35-4}, ISSN = {1868-8969}, year = {2012}, volume = {14}, editor = {D\"{u}rr, Christoph and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.302}, URN = {urn:nbn:de:0030-drops-34078}, doi = {10.4230/LIPIcs.STACS.2012.302}, annote = {Keywords: counting constraint satisfaction problems, approximation, complexity} }
Feedback for Dagstuhl Publishing