Search Results

Documents authored by Sarantis, Michail

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.12
Faster Triangulation Mixing via Transport Flows

Authors: Vedat Levi Alev, Daniel Frishberg, Michail Sarantis, and Prasad Tetali

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

Abstract
We prove an Õ(n²) bound for the relaxation time and the log-Sobolev time (inverse log-Sobolev constant) of the classical triangulation flip chain on a convex (n+2)-gon, implying a mixing time of Õ(n²). The previous state of the art for the mixing time of this chain due to Eppstein and Frishberg [Eppstein and Frishberg, 2023] was Õ(n³), while the best known lower bound on the mixing time due to Molloy, Reed and Steiger [Molloy et al., 1997] is Ω(n^{3/2}). Our relaxation time bound makes significant progress towards Aldous' [Aldous, 2003] conjectured bound of Θ(n^{3/2}) for the relaxation time. We improve upon the analysis of [Eppstein and Frishberg, 2023] by further developing the framework of transport flows introduced in the work [Xiaoyu Chen et al., 2025] of Chen et al. In this light, our results can be seen as a more efficient way of using combinatorial decompositions to obtain functional inequalities for Markov chains. We hope our ideas will find other applications in the future.
Cite as

Vedat Levi Alev, Daniel Frishberg, Michail Sarantis, and Prasad Tetali. Faster Triangulation Mixing via Transport Flows. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{alev_et_al:LIPIcs.ICALP.2026.12,
  author =	{Alev, Vedat Levi and Frishberg, Daniel and Sarantis, Michail and Tetali, Prasad},
  title =	{{Faster Triangulation Mixing via Transport Flows}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{12:1--12:20},
  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.12},
  URN =		{urn:nbn:de:0030-drops-264011},
  doi =		{10.4230/LIPIcs.ICALP.2026.12},
  annote =	{Keywords: triangulations, mixing time, log-Sobolev inequality, spectral gap, Markov chain, random walk, MCMC, transport flow, multicommodity flow}
}
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