Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Jin-Yi Cai and Daniel P. Szabo. Bounded Degree Nonnegative Counting CSP. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 27:1-27:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{cai_et_al:LIPIcs.MFCS.2022.27, author = {Cai, Jin-Yi and Szabo, Daniel P.}, title = {{Bounded Degree Nonnegative Counting CSP}}, booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)}, pages = {27:1--27:16}, 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.27}, URN = {urn:nbn:de:0030-drops-168250}, doi = {10.4230/LIPIcs.MFCS.2022.27}, annote = {Keywords: Computational Counting Complexity, Constraint Satisfaction Problems, Counting CSPs, Complexity Dichotomy, Nonnegative Counting CSP, Graph Homomorphisms} }
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 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Colin Cooper, Martin Dyer, Alan Frieze, and Nicolás Rivera. Discordant Voting Processes on Finite Graphs. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 145:1-145:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{cooper_et_al:LIPIcs.ICALP.2016.145, author = {Cooper, Colin and Dyer, Martin and Frieze, Alan and Rivera, Nicol\'{a}s}, title = {{Discordant Voting Processes on Finite Graphs}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {145:1--145:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.145}, URN = {urn:nbn:de:0030-drops-62898}, doi = {10.4230/LIPIcs.ICALP.2016.145}, annote = {Keywords: Distributed consensus, Voter model, Interacting particles, Randomized algorithm} }
Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Xi Chen, Martin Dyer, Leslie Ann Goldberg, Mark Jerrum, Pinyan Lu, Colin McQuillan, and David Richerby. The complexity of approximating conservative counting CSPs. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 148-159, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2013)
@InProceedings{chen_et_al:LIPIcs.STACS.2013.148, author = {Chen, Xi and Dyer, Martin and Goldberg, Leslie Ann and Jerrum, Mark and Lu, Pinyan and McQuillan, Colin and Richerby, David}, title = {{The complexity of approximating conservative counting CSPs}}, booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)}, pages = {148--159}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-50-7}, ISSN = {1868-8969}, year = {2013}, volume = {20}, editor = {Portier, Natacha 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.2013.148}, URN = {urn:nbn:de:0030-drops-39303}, doi = {10.4230/LIPIcs.STACS.2013.148}, annote = {Keywords: counting constraint satisfaction problem, approximation, 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} }
Published in: Dagstuhl Reports, Volume 1, Issue 6 (2011)
Martin Dyer, Uriel Feige, Alan M. Frieze, and Marek Karpinski. Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241). In Dagstuhl Reports, Volume 1, Issue 6, pp. 24-53, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2011)
@Article{dyer_et_al:DagRep.1.6.24, author = {Dyer, Martin and Feige, Uriel and Frieze, Alan M. and Karpinski, Marek}, title = {{Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241)}}, pages = {24--53}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2011}, volume = {1}, number = {6}, editor = {Dyer, Martin and Feige, Uriel and Frieze, Alan M. and Karpinski, Marek}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.1.6.24}, URN = {urn:nbn:de:0030-drops-32585}, doi = {10.4230/DagRep.1.6.24}, annote = {Keywords: Randomized Algorithms, Approximation Algorithms, Probabilistically Checkable Proofs, Approximation Hardness, Optimization Problems, Counting Problems, Streaming Algorithms, Random Graphs, Hypergraphs, Probabilistic Method, Networks, Linear Programs, Semidefinite Programs} }
Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Martin Dyer and David Richerby. The #CSP Dichotomy is Decidable. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 261-272, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2011)
@InProceedings{dyer_et_al:LIPIcs.STACS.2011.261, author = {Dyer, Martin and Richerby, David}, title = {{The #CSP Dichotomy is Decidable}}, booktitle = {28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)}, pages = {261--272}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-25-5}, ISSN = {1868-8969}, year = {2011}, volume = {9}, editor = {Schwentick, Thomas and D\"{u}rr, Christoph}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.261}, URN = {urn:nbn:de:0030-drops-30161}, doi = {10.4230/LIPIcs.STACS.2011.261}, annote = {Keywords: constraint satisfaction problem, counting problems, complexity dichotomy, decidability} }
Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)
Martin Dyer, Leslie Ann Goldberg, Markus Jalsenius, and David Richerby. The Complexity of Approximating Bounded-Degree Boolean #CSP. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 323-334, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)
@InProceedings{dyer_et_al:LIPIcs.STACS.2010.2466, author = {Dyer, Martin and Goldberg, Leslie Ann and Jalsenius, Markus and Richerby, David}, title = {{The Complexity of Approximating Bounded-Degree Boolean #CSP}}, booktitle = {27th International Symposium on Theoretical Aspects of Computer Science}, pages = {323--334}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-16-3}, ISSN = {1868-8969}, year = {2010}, volume = {5}, editor = {Marion, Jean-Yves and Schwentick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2466}, URN = {urn:nbn:de:0030-drops-24669}, doi = {10.4230/LIPIcs.STACS.2010.2466}, annote = {Keywords: Boolean constraint satisfaction problem, generalized satisfiability, counting, approximation algorithms} }
Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)
Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, and Marc Thurley. A Complexity Dichotomy for Partition Functions with Mixed Signs. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 493-504, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2009)
@InProceedings{goldberg_et_al:LIPIcs.STACS.2009.1821, author = {Goldberg, Leslie Ann and Grohe, Martin and Jerrum, Mark and Thurley, Marc}, title = {{A Complexity Dichotomy for Partition Functions with Mixed Signs}}, booktitle = {26th International Symposium on Theoretical Aspects of Computer Science}, pages = {493--504}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-09-5}, ISSN = {1868-8969}, year = {2009}, volume = {3}, editor = {Albers, Susanne and Marion, Jean-Yves}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1821}, URN = {urn:nbn:de:0030-drops-18217}, doi = {10.4230/LIPIcs.STACS.2009.1821}, annote = {Keywords: Computational complexity} }
Published in: Dagstuhl Seminar Proceedings, Volume 8201, Design and Analysis of Randomized and Approximation Algorithms (2008)
Martin E. Dyer, Mark Jerrum, and Marek Karpinski. 08201 Abstracts Collection – Design and Analysis of Randomized and Approximation Algorithms. In Design and Analysis of Randomized and Approximation Algorithms. Dagstuhl Seminar Proceedings, Volume 8201, pp. 1-19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2008)
@InProceedings{dyer_et_al:DagSemProc.08201.1, author = {Dyer, Martin E. and Jerrum, Mark and Karpinski, Marek}, title = {{08201 Abstracts Collection – Design and Analysis of Randomized and Approximation Algorithms}}, booktitle = {Design and Analysis of Randomized and Approximation Algorithms}, pages = {1--19}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2008}, volume = {8201}, editor = {Martin E. Dyer and Mark Jerrum and Marek Karpinski}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08201.1}, URN = {urn:nbn:de:0030-drops-15518}, doi = {10.4230/DagSemProc.08201.1}, annote = {Keywords: Randomized Algorithms, Approximation Algorithms, Optimization Problems, Measurement Problems, Approximation Complexity, Algorithmic Game Theory, Internet, Decentralized Networks, Network Design} }
Published in: Dagstuhl Seminar Proceedings, Volume 5201, Design and Analysis of Randomized and Approximation Algorithms (2005)
Martin Dyer, Mark Jerrum, and Marek Karpinski. 05201 Abstracts Collection – Design and Analysis of Randomized and Approximation Algorithms. In Design and Analysis of Randomized and Approximation Algorithms. Dagstuhl Seminar Proceedings, Volume 5201, pp. 1-21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2005)
@InProceedings{dyer_et_al:DagSemProc.05201.1, author = {Dyer, Martin and Jerrum, Mark and Karpinski, Marek}, title = {{05201 Abstracts Collection – Design and Analysis of Randomized and Approximation Algorithms}}, booktitle = {Design and Analysis of Randomized and Approximation Algorithms}, pages = {1--21}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2005}, volume = {5201}, editor = {Martin Dyer and Mark Jerrum and Marek Karpinski}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05201.1}, URN = {urn:nbn:de:0030-drops-3191}, doi = {10.4230/DagSemProc.05201.1}, annote = {Keywords: Randomized Algorithms, Approximation Algorithms, Optimization Problems, Measurement Problems, Decentralized Networks} }
Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)
Martin Dyer, Mark Jerrum, and Marek Karpinski. Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 01231). Dagstuhl Seminar Report 309, pp. 1-28, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2002)
@TechReport{dyer_et_al:DagSemRep.309, author = {Dyer, Martin and Jerrum, Mark and Karpinski, Marek}, title = {{Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 01231)}}, pages = {1--28}, ISSN = {1619-0203}, year = {2002}, type = {Dagstuhl Seminar Report}, number = {309}, institution = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.309}, URN = {urn:nbn:de:0030-drops-151930}, doi = {10.4230/DagSemRep.309}, }
Feedback for Dagstuhl Publishing