Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Charilaos Efthymiou and Weiming Feng. On the Mixing Time of Glauber Dynamics for the Hard-Core and Related Models on G(n,d/n). In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 54:1-54:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{efthymiou_et_al:LIPIcs.ICALP.2023.54, author = {Efthymiou, Charilaos and Feng, Weiming}, title = {{On the Mixing Time of Glauber Dynamics for the Hard-Core and Related Models on G(n,d/n)}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {54:1--54:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.54}, URN = {urn:nbn:de:0030-drops-181064}, doi = {10.4230/LIPIcs.ICALP.2023.54}, annote = {Keywords: spin-system, spin-glass, sparse random (hyper)graph, approximate sampling, efficient algorithm} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
David G. Harris and Vladimir Kolmogorov. Parameter Estimation for Gibbs Distributions. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 72:1-72:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{harris_et_al:LIPIcs.ICALP.2023.72, author = {Harris, David G. and Kolmogorov, Vladimir}, title = {{Parameter Estimation for Gibbs Distributions}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {72:1--72:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.72}, URN = {urn:nbn:de:0030-drops-181246}, doi = {10.4230/LIPIcs.ICALP.2023.72}, annote = {Keywords: Gibbs distribution, sampling} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Weiming Feng, Heng Guo, and Jiaheng Wang. Improved Bounds for Randomly Colouring Simple Hypergraphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 25:1-25:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{feng_et_al:LIPIcs.APPROX/RANDOM.2022.25, author = {Feng, Weiming and Guo, Heng and Wang, Jiaheng}, title = {{Improved Bounds for Randomly Colouring Simple Hypergraphs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {25:1--25:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.25}, URN = {urn:nbn:de:0030-drops-171477}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.25}, annote = {Keywords: Approximate counting, Markov chain, Mixing time, Hypergraph colouring} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Andreas Galanis, Leslie Ann Goldberg, Heng Guo, and Kuan Yang. Counting Solutions to Random CNF Formulas. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 53:1-53:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{galanis_et_al:LIPIcs.ICALP.2020.53, author = {Galanis, Andreas and Goldberg, Leslie Ann and Guo, Heng and Yang, Kuan}, title = {{Counting Solutions to Random CNF Formulas}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {53:1--53:14}, 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.53}, URN = {urn:nbn:de:0030-drops-124603}, doi = {10.4230/LIPIcs.ICALP.2020.53}, annote = {Keywords: random CNF formulas, approximate counting} }
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 Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)
Heng Guo and Pinyan Lu. On the Complexity of Holant Problems. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 159-177, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InCollection{guo_et_al:DFU.Vol7.15301.159, author = {Guo, Heng and Lu, Pinyan}, title = {{On the Complexity of Holant Problems}}, booktitle = {The Constraint Satisfaction Problem: Complexity and Approximability}, pages = {159--177}, 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.159}, URN = {urn:nbn:de:0030-drops-69630}, doi = {10.4230/DFU.Vol7.15301.159}, annote = {Keywords: Computational complexity, Counting complexity, Dichotomy theorems, Approximate counting, Holant problems} }
Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Heng Guo and Pinyan Lu. Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 31:1-31:26, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{guo_et_al:LIPIcs.APPROX-RANDOM.2016.31, author = {Guo, Heng and Lu, Pinyan}, title = {{Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)}, pages = {31:1--31:26}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-018-7}, ISSN = {1868-8969}, year = {2016}, volume = {60}, editor = {Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.31}, URN = {urn:nbn:de:0030-drops-66547}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2016.31}, annote = {Keywords: Approximate counting; Ising model; Spin systems; Correlation decay} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, and Daniel Stefankovic. Approximation via Correlation Decay When Strong Spatial Mixing Fails. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 45:1-45:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{bezakova_et_al:LIPIcs.ICALP.2016.45, author = {Bez\'{a}kov\'{a}, Ivona and Galanis, Andreas and Goldberg, Leslie Ann and Guo, Heng and Stefankovic, Daniel}, title = {{Approximation via Correlation Decay When Strong Spatial Mixing Fails}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {45:1--45: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.45}, URN = {urn:nbn:de:0030-drops-63257}, doi = {10.4230/LIPIcs.ICALP.2016.45}, annote = {Keywords: approximate counting, independent sets in hypergraphs, correlation decay} }
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: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Heng Guo, Sangxia Huang, Pinyan Lu, and Mingji Xia. The Complexity of Weighted Boolean #CSP Modulo k. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 249-260, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2011)
@InProceedings{guo_et_al:LIPIcs.STACS.2011.249, author = {Guo, Heng and Huang, Sangxia and Lu, Pinyan and Xia, Mingji}, title = {{The Complexity of Weighted Boolean #CSP Modulo k}}, booktitle = {28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)}, pages = {249--260}, 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.249}, URN = {urn:nbn:de:0030-drops-30158}, doi = {10.4230/LIPIcs.STACS.2011.249}, annote = {Keywords: #CSP, dichotomy theorem, counting problems, computational complexity} }
Feedback for Dagstuhl Publishing