Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Evan Chang, Neel Kolhe, and Youngtak Sohn. Upper Bounds on the 2-Colorability Threshold of Random d-Regular k-Uniform Hypergraphs for k ≥ 3. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 47:1-47:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chang_et_al:LIPIcs.APPROX/RANDOM.2024.47, author = {Chang, Evan and Kolhe, Neel and Sohn, Youngtak}, title = {{Upper Bounds on the 2-Colorability Threshold of Random d-Regular k-Uniform Hypergraphs for k ≥ 3}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {47:1--47:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.47}, URN = {urn:nbn:de:0030-drops-210402}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.47}, annote = {Keywords: Random constraint satisfaction problem, replica symmetry breaking, interpolation bound} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Aiya Kuchukova, Marcus Pappik, Will Perkins, and Corrine Yap. Fast and Slow Mixing of the Kawasaki Dynamics on Bounded-Degree Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 56:1-56:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{kuchukova_et_al:LIPIcs.APPROX/RANDOM.2024.56, author = {Kuchukova, Aiya and Pappik, Marcus and Perkins, Will and Yap, Corrine}, title = {{Fast and Slow Mixing of the Kawasaki Dynamics on Bounded-Degree Graphs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {56:1--56:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.56}, URN = {urn:nbn:de:0030-drops-210493}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.56}, annote = {Keywords: ferromagnetic Ising model, fixed-magnetization Ising model, Kawasaki dynamics, Glauber dynamics, mixing time} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Andreas Galanis, Alkis Kalavasis, and Anthimos Vardis Kandiros. On Sampling from Ising Models with Spectral Constraints. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 70:1-70:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{galanis_et_al:LIPIcs.APPROX/RANDOM.2024.70, author = {Galanis, Andreas and Kalavasis, Alkis and Kandiros, Anthimos Vardis}, title = {{On Sampling from Ising Models with Spectral Constraints}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {70:1--70:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.70}, URN = {urn:nbn:de:0030-drops-210638}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.70}, annote = {Keywords: Ising model, spectral constraints, Glauber dynamics, mean-field Ising, random regular graphs} }
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 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)
Charilaos Efthymiou and Kostas Zampetakis. Broadcasting with Random Matrices. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 55:1-55:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{efthymiou_et_al:LIPIcs.ICALP.2023.55, author = {Efthymiou, Charilaos and Zampetakis, Kostas}, title = {{Broadcasting with Random Matrices}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {55:1--55:14}, 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.55}, URN = {urn:nbn:de:0030-drops-181070}, doi = {10.4230/LIPIcs.ICALP.2023.55}, annote = {Keywords: spin-system, spin-glass, sparse random graph, reconstruction, phase transitions} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Charilaos Efthymiou. On Sampling Symmetric Gibbs Distributions on Sparse Random Graphs and Hypergraphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 57:1-57:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{efthymiou:LIPIcs.ICALP.2022.57, author = {Efthymiou, Charilaos}, title = {{On Sampling Symmetric Gibbs Distributions on Sparse Random Graphs and Hypergraphs}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {57:1--57: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.57}, URN = {urn:nbn:de:0030-drops-163982}, doi = {10.4230/LIPIcs.ICALP.2022.57}, annote = {Keywords: spin-system, spin-glass, sparse random (hyper)graph, approximate sampling, efficient algorithm} }
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 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Amin Coja-Oghlan, Charilaos Efthymiou, Nor Jaafari, Mihyun Kang, and Tobias Kapetanopoulos. Charting the Replica Symmetric Phase. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 40:1-40:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{cojaoghlan_et_al:LIPIcs.APPROX-RANDOM.2017.40, author = {Coja-Oghlan, Amin and Efthymiou, Charilaos and Jaafari, Nor and Kang, Mihyun and Kapetanopoulos, Tobias}, title = {{Charting the Replica Symmetric Phase}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)}, pages = {40:1--40:17}, 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.40}, URN = {urn:nbn:de:0030-drops-75895}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.40}, annote = {Keywords: Random factor graph, bounds for condensation phase transition, Potts antiferromagnet, diluted k-spin model, stochastic block model} }
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} }
Feedback for Dagstuhl Publishing