Search Results

Documents authored by Kuchukova, Aiya

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.134
Sampling Colorings with Fixed Color Class Sizes

Authors: Aiya Kuchukova, Will Perkins, and Xavier Povill

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
In 1970, Hajnal and Szemerédi proved a conjecture of Erdős stating that any graph with maximum degree Δ admits an equitable (Δ+1)-coloring, that is, a coloring where color class sizes differ by at most 1. In 2007 Kierstead and Kostochka reproved their result and provided a polynomial-time algorithm which produces such a coloring. In this paper we study the problem of approximately sampling uniformly random equitable colorings. A series of works gives polynomial-time sampling algorithms for colorings without the color class constraint, the latest improvement being by Carlson and Vigoda for q ≥ 1.809 Δ. In this paper we give a polynomial-time sampling algorithm for equitable colorings when q > 2Δ. Moreover, our results extend to colorings with small deviations from equitable (and as a corollary, establishing their existence). The proof uses the framework of the geometry of polynomials for multivariate polynomials, and as a consequence establishes a multivariate local Central Limit Theorem for color class sizes of uniform random colorings.
Cite as

Aiya Kuchukova, Will Perkins, and Xavier Povill. Sampling Colorings with Fixed Color Class Sizes. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 134:1-134:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kuchukova_et_al:LIPIcs.ICALP.2026.134,
  author =	{Kuchukova, Aiya and Perkins, Will and Povill, Xavier},
  title =	{{Sampling Colorings with Fixed Color Class Sizes}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{134:1--134:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael 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.2026.134},
  URN =		{urn:nbn:de:0030-drops-265231},
  doi =		{10.4230/LIPIcs.ICALP.2026.134},
  annote =	{Keywords: sampling, approximate counting, graph coloring, zero-freeness, Potts model, LCLT}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.56
Fast and Slow Mixing of the Kawasaki Dynamics on Bounded-Degree Graphs

Authors: Aiya Kuchukova, Marcus Pappik, Will Perkins, and Corrine Yap

Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)

Abstract
We study the worst-case mixing time of the global Kawasaki dynamics for the fixed-magnetization Ising model on the class of graphs of maximum degree Δ. Proving a conjecture of Carlson, Davies, Kolla, and Perkins, we show that below the tree uniqueness threshold, the Kawasaki dynamics mix rapidly for all magnetizations. Disproving a conjecture of Carlson, Davies, Kolla, and Perkins, we show that the regime of fast mixing does not extend throughout the regime of tractability for this model: there is a range of parameters for which there exist efficient sampling algorithms for the fixed-magnetization Ising model on max-degree Δ graphs, but the Kawasaki dynamics can take exponential time to mix. Our techniques involve showing spectral independence in the fixed-magnetization Ising model and proving a sharp threshold for the existence of multiple metastable states in the Ising model with external field on random regular graphs.
Cite as

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)

Copy BibTex To Clipboard

@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}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact