Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Konrad Anand, Andreas Göbel, Marcus Pappik, and Will Perkins. Perfect Sampling for Hard Spheres from Strong Spatial Mixing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 38:1-38:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{anand_et_al:LIPIcs.APPROX/RANDOM.2023.38, author = {Anand, Konrad and G\"{o}bel, Andreas and Pappik, Marcus and Perkins, Will}, title = {{Perfect Sampling for Hard Spheres from Strong Spatial Mixing}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {38:1--38:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-296-9}, ISSN = {1868-8969}, year = {2023}, volume = {275}, editor = {Megow, Nicole and Smith, Adam}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.38}, URN = {urn:nbn:de:0030-drops-188638}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.38}, annote = {Keywords: perfect sampling, hard-sphere model, Gibbs point processes} }
Published in: Dagstuhl Reports, Volume 12, Issue 11 (2023)
Holger Dell, Mark R. Jerrum, Haiko Müller, Konrad Anand, and Marcus Pappik. Counting and Sampling: Algorithms and Complexity (Dagstuhl Seminar 22482). In Dagstuhl Reports, Volume 12, Issue 11, pp. 124-145, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@Article{dell_et_al:DagRep.12.11.124, author = {Dell, Holger and Jerrum, Mark R. and M\"{u}ller, Haiko and Anand, Konrad and Pappik, Marcus}, title = {{Counting and Sampling: Algorithms and Complexity (Dagstuhl Seminar 22482)}}, pages = {124--145}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2023}, volume = {12}, number = {11}, editor = {Dell, Holger and Jerrum, Mark R. and M\"{u}ller, Haiko and Anand, Konrad and Pappik, Marcus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.11.124}, URN = {urn:nbn:de:0030-drops-178394}, doi = {10.4230/DagRep.12.11.124}, annote = {Keywords: Sampling, Counting, Algorithms, Complexity, Statistical Physics, Phase Transitions, Markov Chains, Graphs, Point Processes} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Arkadev Chattopadhyay, Rajit Datta, Utsab Ghosal, and Partha Mukhopadhyay. Monotone Complexity of Spanning Tree Polynomial Re-Visited. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 39:1-39:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{chattopadhyay_et_al:LIPIcs.ITCS.2022.39, author = {Chattopadhyay, Arkadev and Datta, Rajit and Ghosal, Utsab and Mukhopadhyay, Partha}, title = {{Monotone Complexity of Spanning Tree Polynomial Re-Visited}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {39:1--39:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.39}, URN = {urn:nbn:de:0030-drops-156356}, doi = {10.4230/LIPIcs.ITCS.2022.39}, annote = {Keywords: Spanning Tree Polynomial, Monotone Computation, Lower Bounds, Communication Complexity} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Farzam Ebrahimnejad, Ansh Nagda, and Shayan Oveis Gharan. Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 61:1-61:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{ebrahimnejad_et_al:LIPIcs.ITCS.2022.61, author = {Ebrahimnejad, Farzam and Nagda, Ansh and Gharan, Shayan Oveis}, title = {{Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {61:1--61:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.61}, URN = {urn:nbn:de:0030-drops-156579}, doi = {10.4230/LIPIcs.ITCS.2022.61}, annote = {Keywords: perfect matchings, approximate sampling, approximate counting, expanders} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Heng Guo and Mark Jerrum. A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 68:1-68:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{guo_et_al:LIPIcs.ICALP.2018.68, author = {Guo, Heng and Jerrum, Mark}, title = {{A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {68:1--68:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.68}, URN = {urn:nbn:de:0030-drops-90727}, doi = {10.4230/LIPIcs.ICALP.2018.68}, annote = {Keywords: Approximate counting, Network Reliability, Sampling, Markov chains} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Heng Guo and Mark Jerrum. Perfect Simulation of the Hard Disks Model by Partial Rejection Sampling. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 69:1-69:10, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{guo_et_al:LIPIcs.ICALP.2018.69, author = {Guo, Heng and Jerrum, Mark}, title = {{Perfect Simulation of the Hard Disks Model by Partial Rejection Sampling}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {69:1--69:10}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.69}, URN = {urn:nbn:de:0030-drops-90739}, doi = {10.4230/LIPIcs.ICALP.2018.69}, annote = {Keywords: Hard disks model, Sampling, Markov chains} }
Published in: Dagstuhl Reports, Volume 7, Issue 8 (2018)
Ivona Bezáková, Leslie Ann Goldberg, and Mark R. Jerrum. Computational Counting (Dagstuhl Seminar 17341). In Dagstuhl Reports, Volume 7, Issue 8, pp. 23-44, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@Article{bezakova_et_al:DagRep.7.8.23, author = {Bez\'{a}kov\'{a}, Ivona and Goldberg, Leslie Ann and Jerrum, Mark R.}, title = {{Computational Counting (Dagstuhl Seminar 17341)}}, pages = {23--44}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2018}, volume = {7}, number = {8}, editor = {Bez\'{a}kov\'{a}, Ivona and Goldberg, Leslie Ann and Jerrum, Mark R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.7.8.23}, URN = {urn:nbn:de:0030-drops-84283}, doi = {10.4230/DagRep.7.8.23}, annote = {Keywords: approximation algorithms, computational complexity, counting problems, partition functions, phase transitions} }
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.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: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Andreas Galanis, Leslie Ann Goldberg, and Mark Jerrum. A Complexity Trichotomy for Approximately Counting List H-Colourings. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 46:1-46:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{galanis_et_al:LIPIcs.ICALP.2016.46, author = {Galanis, Andreas and Goldberg, Leslie Ann and Jerrum, Mark}, title = {{A Complexity Trichotomy for Approximately Counting List H-Colourings}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {46:1--46: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.46}, URN = {urn:nbn:de:0030-drops-63262}, doi = {10.4230/LIPIcs.ICALP.2016.46}, annote = {Keywords: approximate counting, graph homomorphisms, list colourings} }
Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel Stefankovic, and Eric Vigoda. #BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Non-uniqueness Region. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 582-595, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)
@InProceedings{cai_et_al:LIPIcs.APPROX-RANDOM.2014.582, author = {Cai, Jin-Yi and Galanis, Andreas and Goldberg, Leslie Ann and Guo, Heng and Jerrum, Mark and Stefankovic, Daniel and Vigoda, Eric}, title = {{#BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Non-uniqueness Region}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)}, pages = {582--595}, 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.582}, URN = {urn:nbn:de:0030-drops-47235}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2014.582}, annote = {Keywords: Spin systems, approximate counting, complexity, #BIS-hardness, phase transition} }
Published in: Dagstuhl Reports, Volume 3, Issue 1 (2013)
Peter Bürgisser, Leslie Ann Goldberg, Mark Jerrum, and Pascal Koiran. Computational Counting (Dagstuhl Seminar 13031). In Dagstuhl Reports, Volume 3, Issue 1, pp. 47-66, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2013)
@Article{burgisser_et_al:DagRep.3.1.47, author = {B\"{u}rgisser, Peter and Goldberg, Leslie Ann and Jerrum, Mark and Koiran, Pascal}, title = {{Computational Counting (Dagstuhl Seminar 13031)}}, pages = {47--66}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2013}, volume = {3}, number = {1}, editor = {B\"{u}rgisser, Peter and Goldberg, Leslie Ann and Jerrum, Mark and Koiran, Pascal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.3.1.47}, URN = {urn:nbn:de:0030-drops-40087}, doi = {10.4230/DagRep.3.1.47}, annote = {Keywords: Computational complexity, counting problems, graph polynomials, holographic algorithms, statistical physics, constraint satisfaction} }
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 Seminar Proceedings, Volume 10481, Computational Counting (2011)
Peter Bürgisser, Leslie Ann Goldberg, and Mark Jerrum. 10481 Abstracts Collection – Computational Counting. In Computational Counting. Dagstuhl Seminar Proceedings, Volume 10481, pp. 1-15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2011)
@InProceedings{burgisser_et_al:DagSemProc.10481.1, author = {B\"{u}rgisser, Peter and Goldberg, Leslie Ann and Jerrum, Mark}, title = {{10481 Abstracts Collection – Computational Counting}}, booktitle = {Computational Counting}, pages = {1--15}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2011}, volume = {10481}, editor = {Peter B\"{u}rgisser and Leslie Ann Goldberg and Mark Jerrum}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10481.1}, URN = {urn:nbn:de:0030-drops-29453}, doi = {10.4230/DagSemProc.10481.1}, annote = {Keywords: Computational complexity, counting problems, holographic algorithms, statistical physics, constraint satisfaction} }
Published in: Dagstuhl Seminar Proceedings, Volume 10481, Computational Counting (2011)
Peter Bürgisser, Leslie Ann Goldberg, and Mark Jerrum. 10481 Executive Summary – Computational Counting. In Computational Counting. Dagstuhl Seminar Proceedings, Volume 10481, pp. 1-3, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2011)
@InProceedings{burgisser_et_al:DagSemProc.10481.2, author = {B\"{u}rgisser, Peter and Goldberg, Leslie Ann and Jerrum, Mark}, title = {{10481 Executive Summary – Computational Counting}}, booktitle = {Computational Counting}, pages = {1--3}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2011}, volume = {10481}, editor = {Peter B\"{u}rgisser and Leslie Ann Goldberg and Mark Jerrum}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10481.2}, URN = {urn:nbn:de:0030-drops-29441}, doi = {10.4230/DagSemProc.10481.2}, annote = {Keywords: Computational complexity, counting problems, holographic algorithms, statistical physics, constraint satisfaction} }
Feedback for Dagstuhl Publishing