Search Results

Documents authored by Alev, Vedat Levi

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
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.58
Expanderizing Higher Order Random Walks

Authors: Vedat Levi Alev and Shravas Rao

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

Abstract
We study a variant of the down-up (also known as the Glauber dynamics) and up-down walks over an n-partite simplicial complex, which we call expanderized higher order random walks - where the sequence of updated coordinates correspond to the sequence of vertices visited by a random walk over an auxiliary expander graph H. When H is the clique with self loops on [n], this random walk reduces to the usual down-up walk and when H is the directed cycle on [n], this random walk reduces to the well-known systematic scan Glauber dynamics. We show that whenever the usual higher order random walks satisfy a log-Sobolev inequality or a Poincaré inequality, the expanderized walks satisfy the same inequalities with a loss of quality related to the two-sided expansion of the auxillary graph H. Our construction can be thought as a higher order random walk generalization of the derandomized squaring algorithm of Rozenman and Vadhan (RANDOM 2005). We study the mixing times of our expanderized walks in two example cases: We show that when initiated with an expander graph our expanderized random walks have mixing time (i) O(n log n) for sampling a uniformly random list colorings of a graph G of maximum degree Δ = O(1) where each vertex has at least (11/6 - ε) Δ and at most O(Δ) colors, (ii) O_h((n log n)/(1 - ‖J‖_op)²) for sampling the Ising model with a PSD interaction matrix J ∈ ℝ^{n×n} satisfying ‖J‖_op ≤ 1 and the external field h ∈ ℝⁿ- here the O(•) notation hides a constant that depends linearly on the largest entry of h. As expander graphs can be very sparse, this decreases the amount of randomness required to simulate the down-up walks by a logarithmic factor. We also prove some simple results which enable us to argue about log-Sobolev constants of higher order random walks and provide a simple and self-contained analysis of local-to-global Φ-entropy contraction in simplicial complexes - giving simpler proofs for many pre-existing results.
Cite as

Vedat Levi Alev and Shravas Rao. Expanderizing Higher Order Random Walks. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 58:1-58:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{alev_et_al:LIPIcs.APPROX/RANDOM.2024.58,
  author =	{Alev, Vedat Levi and Rao, Shravas},
  title =	{{Expanderizing Higher Order Random Walks}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{58:1--58: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.58},
  URN =		{urn:nbn:de:0030-drops-210510},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.58},
  annote =	{Keywords: Higher Order Random Walks, Expander Graphs, Glauber Dynamics, Derandomized Squaring, High Dimensional Expansion, Spectral Independence, Entropic Independence}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2018.41
Graph Clustering using Effective Resistance

Authors: Vedat Levi Alev, Nima Anari, Lap Chi Lau, and Shayan Oveis Gharan

Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)

Abstract
We design a polynomial time algorithm that for any weighted undirected graph G = (V, E, w) and sufficiently large \delta > 1, partitions V into subsets V(1),..., V(h) for some h>= 1, such that at most \delta^{-1} fraction of the weights are between clusters, i.e. sum(i < j) |E(V(i), V(j)| < w(E)/\delta and the effective resistance diameter of each of the induced subgraphs G[V(i)] is at most \delta^3 times the inverse of the average weighted degree, i.e. max{ Reff(u, v) : u, v \in V(i)} < \delta^3 · |V|/w(E) for all i = 1,..., h. In particular, it is possible to remove one percent of weight of edges of any given graph such that each of the resulting connected components has effective resistance diameter at most the inverse of the average weighted degree. Our proof is based on a new connection between effective resistance and low conductance sets. We show that if the effective resistance between two vertices u and v is large, then there must be a low conductance cut separating u from v. This implies that very mildly expanding graphs have constant effective resistance diameter. We believe that this connection could be of independent interest in algorithm design.
Cite as

Vedat Levi Alev, Nima Anari, Lap Chi Lau, and Shayan Oveis Gharan. Graph Clustering using Effective Resistance. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 41:1-41:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{alev_et_al:LIPIcs.ITCS.2018.41,
  author =	{Alev, Vedat Levi and Anari, Nima and Lau, Lap Chi and Oveis Gharan, Shayan},
  title =	{{Graph Clustering using Effective Resistance}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{41:1--41:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Karlin, Anna R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.41},
  URN =		{urn:nbn:de:0030-drops-83696},
  doi =		{10.4230/LIPIcs.ITCS.2018.41},
  annote =	{Keywords: Electrical Flows, Effective Resistance, Conductance, Graph Partitioning}
}
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