Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Tim Seppelt. An Algorithmic Meta Theorem for Homomorphism Indistinguishability. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 82:1-82:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{seppelt:LIPIcs.MFCS.2024.82, author = {Seppelt, Tim}, title = {{An Algorithmic Meta Theorem for Homomorphism Indistinguishability}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {82:1--82:19}, 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.82}, URN = {urn:nbn:de:0030-drops-206387}, doi = {10.4230/LIPIcs.MFCS.2024.82}, annote = {Keywords: homomorphism indistinguishability, graph homomorphism, graph minor, recognisability, randomised algorithm, Courcelle’s Theorem} }
Published in: LIPIcs, Volume 304, 5th Conference on Information-Theoretic Cryptography (ITC 2024)
Benny Applebaum, Kaartik Bhushan, and Manoj Prabhakaran. Communication Complexity vs Randomness Complexity in Interactive Proofs. In 5th Conference on Information-Theoretic Cryptography (ITC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 304, pp. 2:1-2:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{applebaum_et_al:LIPIcs.ITC.2024.2, author = {Applebaum, Benny and Bhushan, Kaartik and Prabhakaran, Manoj}, title = {{Communication Complexity vs Randomness Complexity in Interactive Proofs}}, booktitle = {5th Conference on Information-Theoretic Cryptography (ITC 2024)}, pages = {2:1--2:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-333-1}, ISSN = {1868-8969}, year = {2024}, volume = {304}, editor = {Aggarwal, Divesh}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2024.2}, URN = {urn:nbn:de:0030-drops-205103}, doi = {10.4230/LIPIcs.ITC.2024.2}, annote = {Keywords: Interactive Proof Systems, Communication Complexity, Hash Functions, Pseudo-Random Generators, Compression} }
Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
Takehide Soh, Takumu Watanabe, Jun Kawahara, Akira Suzuki, and Takehiro Ito. Scalable Hard Instances for Independent Set Reconfiguration. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{soh_et_al:LIPIcs.SEA.2024.26, author = {Soh, Takehide and Watanabe, Takumu and Kawahara, Jun and Suzuki, Akira and Ito, Takehiro}, title = {{Scalable Hard Instances for Independent Set Reconfiguration}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {26:1--26:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-325-6}, ISSN = {1868-8969}, year = {2024}, volume = {301}, editor = {Liberti, Leo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.26}, URN = {urn:nbn:de:0030-drops-203913}, doi = {10.4230/LIPIcs.SEA.2024.26}, annote = {Keywords: Combinatorial reconfiguration, Benckmark dataset, Graph Algorithm, PSPACE-complete} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Konrad Anand, Weiming Feng, Graham Freifeld, Heng Guo, and Jiaheng Wang. Approximate Counting for Spin Systems in Sub-Quadratic Time. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{anand_et_al:LIPIcs.ICALP.2024.11, author = {Anand, Konrad and Feng, Weiming and Freifeld, Graham and Guo, Heng and Wang, Jiaheng}, title = {{Approximate Counting for Spin Systems in Sub-Quadratic Time}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {11:1--11: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.11}, URN = {urn:nbn:de:0030-drops-201543}, doi = {10.4230/LIPIcs.ICALP.2024.11}, annote = {Keywords: Randomised algorithm, Approximate counting, Spin system, Sub-quadratic algorithm} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Charlie Carlson, Ewan Davies, Alexandra Kolla, and Aditya Potukuchi. A Spectral Approach to Approximately Counting Independent Sets in Dense Bipartite Graphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 35:1-35:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{carlson_et_al:LIPIcs.ICALP.2024.35, author = {Carlson, Charlie and Davies, Ewan and Kolla, Alexandra and Potukuchi, Aditya}, title = {{A Spectral Approach to Approximately Counting Independent Sets in Dense Bipartite Graphs}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {35:1--35: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.35}, URN = {urn:nbn:de:0030-drops-201782}, doi = {10.4230/LIPIcs.ICALP.2024.35}, annote = {Keywords: approximate counting, independent sets, bipartite graphs, graph containers} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Weiming Feng and Heng Guo. An FPRAS for Two Terminal Reliability in Directed Acyclic Graphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 62:1-62:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{feng_et_al:LIPIcs.ICALP.2024.62, author = {Feng, Weiming and Guo, Heng}, title = {{An FPRAS for Two Terminal Reliability in Directed Acyclic Graphs}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {62:1--62:19}, 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.62}, URN = {urn:nbn:de:0030-drops-202057}, doi = {10.4230/LIPIcs.ICALP.2024.62}, annote = {Keywords: Approximate counting, Network reliability, Sampling algorithm} }
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} }