Search Results

Documents authored by Tetali, Prasad

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}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2017.16
Mutation, Sexual Reproduction and Survival in Dynamic Environments

Authors: Ruta Mehta, Ioannis Panageas, Georgios Piliouras, Prasad Tetali, and Vijay V. Vazirani

Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

Abstract
A new approach to understanding evolution [Valiant, JACM 2009], namely viewing it through the lens of computation, has already started yielding new insights, e.g., natural selection under sexual reproduction can be interpreted as the Multiplicative Weight Update (MWU) Algorithm in coordination games played among genes [Chastain, Livnat, Papadimitriou, Vazirani, PNAS 2014]. Using this machinery, we study the role of mutation in changing environments in the presence of sexual reproduction. Following [Wolf, Vazirani, Arkin, J. Theor. Biology], we model changing environments via a Markov chain, with the states representing environments, each with its own fitness matrix. In this setting, we show that in the absence of mutation, the population goes extinct, but in the presence of mutation, the population survives with positive probability. On the way to proving the above theorem, we need to establish some facts about dynamics in games. We provide the first, to our knowledge, polynomial convergence bound for noisy MWU in a coordination game. Finally, we also show that in static environments, sexual evolution with mutation converges, for any level of mutation.
Cite as

Ruta Mehta, Ioannis Panageas, Georgios Piliouras, Prasad Tetali, and Vijay V. Vazirani. Mutation, Sexual Reproduction and Survival in Dynamic Environments. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 16:1-16:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{mehta_et_al:LIPIcs.ITCS.2017.16,
  author =	{Mehta, Ruta and Panageas, Ioannis and Piliouras, Georgios and Tetali, Prasad and Vazirani, Vijay V.},
  title =	{{Mutation, Sexual Reproduction and Survival in Dynamic Environments}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{16:1--16:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Papadimitriou, Christos H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.16},
  URN =		{urn:nbn:de:0030-drops-81655},
  doi =		{10.4230/LIPIcs.ITCS.2017.16},
  annote =	{Keywords: Evolution, Non-linear dynamics, Mutation}
}
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