Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Charilaos Efthymiou, Thomas P. Hayes, Daniel Štefankovič, and Eric Vigoda. Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{efthymiou_et_al:LIPIcs.APPROX/RANDOM.2023.33, author = {Efthymiou, Charilaos and Hayes, Thomas P. and \v{S}tefankovi\v{c}, Daniel and Vigoda, Eric}, title = {{Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {33:1--33:16}, 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.33}, URN = {urn:nbn:de:0030-drops-188589}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.33}, annote = {Keywords: MCMC, Mixing Time, Independent Sets, Hard-Core Model, Approximate Counting Algorithms, Sampling Algorithms} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, and Daniel Štefankovič. Fast Sampling via Spectral Independence Beyond Bounded-Degree Graphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 21:1-21:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bezakova_et_al:LIPIcs.ICALP.2022.21, author = {Bez\'{a}kov\'{a}, Ivona and Galanis, Andreas and Goldberg, Leslie Ann and \v{S}tefankovi\v{c}, Daniel}, title = {{Fast Sampling via Spectral Independence Beyond Bounded-Degree Graphs}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {21:1--21: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.21}, URN = {urn:nbn:de:0030-drops-163622}, doi = {10.4230/LIPIcs.ICALP.2022.21}, annote = {Keywords: Hard-core model, Random graphs, Markov chains} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Amin Coja-Oghlan, Andreas Galanis, Leslie Ann Goldberg, Jean Bernoulli Ravelomanana, Daniel Štefankovič, and Eric Vigoda. Metastability of the Potts Ferromagnet on Random Regular Graphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 45:1-45:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{cojaoghlan_et_al:LIPIcs.ICALP.2022.45, author = {Coja-Oghlan, Amin and Galanis, Andreas and Goldberg, Leslie Ann and Ravelomanana, Jean Bernoulli and \v{S}tefankovi\v{c}, Daniel and Vigoda, Eric}, title = {{Metastability of the Potts Ferromagnet on Random Regular Graphs}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {45:1--45:20}, 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.45}, URN = {urn:nbn:de:0030-drops-163865}, doi = {10.4230/LIPIcs.ICALP.2022.45}, annote = {Keywords: Markov chains, sampling, random regular graph, Potts model} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Andreas Galanis, Daniel Štefankovič, and Eric Vigoda. Approximating Observables Is as Hard as Counting. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 63:1-63:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{galanis_et_al:LIPIcs.ICALP.2022.63, author = {Galanis, Andreas and \v{S}tefankovi\v{c}, Daniel and Vigoda, Eric}, title = {{Approximating Observables Is as Hard as Counting}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {63:1--63:18}, 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.63}, URN = {urn:nbn:de:0030-drops-164047}, doi = {10.4230/LIPIcs.ICALP.2022.63}, annote = {Keywords: Approximate Counting, Averages, Phase Transitions, Random Structures} }
Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)
Niloufar Fuladi, Alfredo Hubard, and Arnaud de Mesmay. Short Topological Decompositions of Non-Orientable Surfaces. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 41:1-41:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{fuladi_et_al:LIPIcs.SoCG.2022.41, author = {Fuladi, Niloufar and Hubard, Alfredo and de Mesmay, Arnaud}, title = {{Short Topological Decompositions of Non-Orientable Surfaces}}, booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)}, pages = {41:1--41:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-227-3}, ISSN = {1868-8969}, year = {2022}, volume = {224}, editor = {Goaoc, Xavier and Kerber, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.41}, URN = {urn:nbn:de:0030-drops-160492}, doi = {10.4230/LIPIcs.SoCG.2022.41}, annote = {Keywords: Computational topology, embedded graph, non-orientable surface, joint crossing number, canonical system of loop, surface decomposition} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Antonio Blanca, Zongchen Chen, Daniel Štefankovič, and Eric Vigoda. The Swendsen-Wang Dynamics on Trees. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 43:1-43:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{blanca_et_al:LIPIcs.APPROX/RANDOM.2021.43, author = {Blanca, Antonio and Chen, Zongchen and \v{S}tefankovi\v{c}, Daniel and Vigoda, Eric}, title = {{The Swendsen-Wang Dynamics on Trees}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {43:1--43:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.43}, URN = {urn:nbn:de:0030-drops-147366}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.43}, annote = {Keywords: Markov Chains, mixing times, Ising and Potts models, Swendsen-Wang dynamics, trees} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Charilaos Efthymiou, Andreas Galanis, Thomas P. Hayes, Daniel Štefankovič, and Eric Vigoda. Improved Strong Spatial Mixing for Colorings on Trees. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 48:1-48:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{efthymiou_et_al:LIPIcs.APPROX-RANDOM.2019.48, author = {Efthymiou, Charilaos and Galanis, Andreas and Hayes, Thomas P. and \v{S}tefankovi\v{c}, Daniel and Vigoda, Eric}, title = {{Improved Strong Spatial Mixing for Colorings on Trees}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {48:1--48:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.48}, URN = {urn:nbn:de:0030-drops-112630}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.48}, annote = {Keywords: colorings, regular tree, spatial mixing, phase transitions} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, and Daniel Štefankovič. The Complexity of Approximating the Matching Polynomial in the Complex Plane. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 22:1-22:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bezakova_et_al:LIPIcs.ICALP.2019.22, author = {Bez\'{a}kov\'{a}, Ivona and Galanis, Andreas and Goldberg, Leslie Ann and \v{S}tefankovi\v{c}, Daniel}, title = {{The Complexity of Approximating the Matching Polynomial in the Complex Plane}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {22:1--22:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.22}, URN = {urn:nbn:de:0030-drops-105983}, doi = {10.4230/LIPIcs.ICALP.2019.22}, annote = {Keywords: matchings, partition function, correlation decay, connective constant} }
Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Antonio Blanca, Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic, Eric Vigoda, and Kuan Yang. Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 33:1-33:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{blanca_et_al:LIPIcs.APPROX-RANDOM.2018.33, author = {Blanca, Antonio and Galanis, Andreas and Goldberg, Leslie Ann and Stefankovic, Daniel and Vigoda, Eric and Yang, Kuan}, title = {{Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)}, pages = {33:1--33:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-085-9}, ISSN = {1868-8969}, year = {2018}, volume = {116}, editor = {Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.33}, URN = {urn:nbn:de:0030-drops-94371}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2018.33}, annote = {Keywords: sampling, Potts model, random regular graphs, phase transitions} }
Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Rupam Acharyya and Daniel Stefankovic. Glauber Dynamics for Ising Model on Convergent Dense Graph Sequences. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{acharyya_et_al:LIPIcs.APPROX-RANDOM.2017.23, author = {Acharyya, Rupam and Stefankovic, Daniel}, title = {{Glauber Dynamics for Ising Model on Convergent Dense Graph Sequences}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)}, pages = {23:1--23:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-044-6}, ISSN = {1868-8969}, year = {2017}, volume = {81}, editor = {Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.23}, URN = {urn:nbn:de:0030-drops-75724}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.23}, annote = {Keywords: Spin systems, Glauber dynamics, Ising model, graphons} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Andreas Galanis, Leslie Ann Goldberg, and Daniel Stefankovic. Inapproximability of the Independent Set Polynomial Below the Shearer Threshold. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 28:1-28:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{galanis_et_al:LIPIcs.ICALP.2017.28, author = {Galanis, Andreas and Goldberg, Leslie Ann and Stefankovic, Daniel}, title = {{Inapproximability of the Independent Set Polynomial Below the Shearer Threshold}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {28:1--28:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.28}, URN = {urn:nbn:de:0030-drops-73962}, doi = {10.4230/LIPIcs.ICALP.2017.28}, annote = {Keywords: approximate counting, independent set polynomial, Shearer threshold} }
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 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Andreas Galanis, Daniel Štefankovic, and Eric Vigoda. Swendsen-Wang Algorithm on the Mean-Field Potts Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 815-828, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{galanis_et_al:LIPIcs.APPROX-RANDOM.2015.815, author = {Galanis, Andreas and \v{S}tefankovic, Daniel and Vigoda, Eric}, title = {{Swendsen-Wang Algorithm on the Mean-Field Potts Model}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)}, pages = {815--828}, 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.815}, URN = {urn:nbn:de:0030-drops-53389}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2015.815}, annote = {Keywords: Ferromagnetic Potts model, Swendsen-Wang dynamics, mixing time, mean-field analysis, phase transition.} }
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 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Andreas Galanis, Daniel Stefankovic, Eric Vigoda, and Linji Yang. Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 677-691, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{galanis_et_al:LIPIcs.APPROX-RANDOM.2014.677, author = {Galanis, Andreas and Stefankovic, Daniel and Vigoda, Eric and Yang, Linji}, title = {{Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)}, pages = {677--691}, 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.677}, URN = {urn:nbn:de:0030-drops-47319}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2014.677}, annote = {Keywords: Ferromagnetic Potts model, approximate counting, spin systems, phase transition, random regular graphs} }
Feedback for Dagstuhl Publishing