Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Guoliang Qiu, Yanheng Wang, and Chihao Zhang. A Perfect Sampler for Hypergraph Independent Sets. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 103:1-103:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{qiu_et_al:LIPIcs.ICALP.2022.103, author = {Qiu, Guoliang and Wang, Yanheng and Zhang, Chihao}, title = {{A Perfect Sampler for Hypergraph Independent Sets}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {103:1--103:16}, 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.103}, URN = {urn:nbn:de:0030-drops-164442}, doi = {10.4230/LIPIcs.ICALP.2022.103}, annote = {Keywords: Coupling from the past, Markov chains, Hypergraph independent sets} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Nima Anari, Michał Dereziński, Thuy-Duong Vuong, and Elizabeth Yang. Domain Sparsification of Discrete Distributions Using Entropic Independence. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 5:1-5:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{anari_et_al:LIPIcs.ITCS.2022.5, author = {Anari, Nima and Derezi\'{n}ski, Micha{\l} and Vuong, Thuy-Duong and Yang, Elizabeth}, title = {{Domain Sparsification of Discrete Distributions Using Entropic Independence}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {5:1--5:23}, 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.5}, URN = {urn:nbn:de:0030-drops-156013}, doi = {10.4230/LIPIcs.ITCS.2022.5}, annote = {Keywords: Domain Sparsification, Markov Chains, Sampling, Entropic Independence} }
Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Yitong Yin and Chihao Zhang. Sampling in Potts Model on Sparse Random Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 47:1-47:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{yin_et_al:LIPIcs.APPROX-RANDOM.2016.47, author = {Yin, Yitong and Zhang, Chihao}, title = {{Sampling in Potts Model on Sparse Random Graphs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)}, pages = {47:1--47:22}, 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.47}, URN = {urn:nbn:de:0030-drops-66706}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2016.47}, annote = {Keywords: Potts model, Sampling, Random Graph, Approximation Algorithm} }
Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
Pinyan Lu, Kuan Yang, and Chihao Zhang. FPTAS for Hardcore and Ising Models on Hypergraphs. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 51:1-51:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{lu_et_al:LIPIcs.STACS.2016.51, author = {Lu, Pinyan and Yang, Kuan and Zhang, Chihao}, title = {{FPTAS for Hardcore and Ising Models on Hypergraphs}}, booktitle = {33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)}, pages = {51:1--51:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-001-9}, ISSN = {1868-8969}, year = {2016}, volume = {47}, editor = {Ollinger, Nicolas and Vollmer, Heribert}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.51}, URN = {urn:nbn:de:0030-drops-57526}, doi = {10.4230/LIPIcs.STACS.2016.51}, annote = {Keywords: hard-core model, ising model, hypergraph, spatial mixing, correlation decay} }
Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Amin Coja-Oghlan, Charilaos Efthymiou, and Nor Jaafari. Local Convergence of Random Graph Colorings. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 726-737, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{cojaoghlan_et_al:LIPIcs.APPROX-RANDOM.2015.726, author = {Coja-Oghlan, Amin and Efthymiou, Charilaos and Jaafari, Nor}, title = {{Local Convergence of Random Graph Colorings}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)}, pages = {726--737}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-89-7}, ISSN = {1868-8969}, year = {2015}, volume = {40}, editor = {Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.726}, URN = {urn:nbn:de:0030-drops-53321}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2015.726}, annote = {Keywords: Random graph, Galton-Watson tree, phase transitions, graph coloring, Gibbs distribution, convergence} }
Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Charilaos Efthymiou. Reconstruction/Non-reconstruction Thresholds for Colourings of General Galton-Watson Trees. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 756-774, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{efthymiou:LIPIcs.APPROX-RANDOM.2015.756, author = {Efthymiou, Charilaos}, title = {{Reconstruction/Non-reconstruction Thresholds for Colourings of General Galton-Watson Trees}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)}, pages = {756--774}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-89-7}, ISSN = {1868-8969}, year = {2015}, volume = {40}, editor = {Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.756}, URN = {urn:nbn:de:0030-drops-53346}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2015.756}, annote = {Keywords: Random Colouring, Reconstruction Problem, Galton-Watson Tree} }
Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Jingcheng Liu, Pinyan Lu, and Chihao Zhang. The Complexity of Ferromagnetic Two-spin Systems with External Fields. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 843-856, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{liu_et_al:LIPIcs.APPROX-RANDOM.2014.843, author = {Liu, Jingcheng and Lu, Pinyan and Zhang, Chihao}, title = {{The Complexity of Ferromagnetic Two-spin Systems with External Fields}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)}, pages = {843--856}, 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.843}, URN = {urn:nbn:de:0030-drops-47428}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2014.843}, annote = {Keywords: Spin System, #BIS-hard, FPRAS} }
Feedback for Dagstuhl Publishing