6 Search Results for "Zanetti, Luca"

Document
DOI: 10.4230/LIPIcs.STACS.2026.38
Fully Dynamic Spectral Sparsification for Directed Hypergraphs

Authors: Sebastian Forster, Gramoz Goranci, and Ali Momeni

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
There has been a surge of interest in spectral hypergraph sparsification, a natural generalization of spectral sparsification for graphs. In this paper, we present a simple fully dynamic algorithm for maintaining spectral hypergraph sparsifiers of directed hypergraphs. Our algorithm achieves a near-optimal size of O(n² / ε ² log ⁷ m) and amortized update time of O(r² log ³ m), where n is the number of vertices, and m and r respectively upper bound the number of hyperedges and the rank of the hypergraph at any time. We also extend our approach to the parallel batch-dynamic setting, where a batch of any k hyperedge insertions or deletions can be processed with O(kr² log ³ m) amortized work and O(log ² m) depth. This constitutes the first spectral-based sparsification algorithm in this setting.
Cite as

Sebastian Forster, Gramoz Goranci, and Ali Momeni. Fully Dynamic Spectral Sparsification for Directed Hypergraphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 38:1-38:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{forster_et_al:LIPIcs.STACS.2026.38,
  author =	{Forster, Sebastian and Goranci, Gramoz and Momeni, Ali},
  title =	{{Fully Dynamic Spectral Sparsification for Directed Hypergraphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{38:1--38:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.38},
  URN =		{urn:nbn:de:0030-drops-255272},
  doi =		{10.4230/LIPIcs.STACS.2026.38},
  annote =	{Keywords: Spectral sparsification, Dynamic algorithms, (Directed) hypergraphs, Data structures}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.71
Broadcast in Almost Mixing Time

Authors: Anton Paramonov and Roger Wattenhofer

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
We study the problem of broadcasting multiple messages in the CONGEST model. In this problem, a dedicated source node s possesses a set M of messages with every message of size O(log n) where n is the total number of nodes. The objective is to ensure that every node in the network learns all messages in M. The execution of an algorithm progresses in rounds, and we focus on optimizing the round complexity of broadcasting multiple messages. Our primary contribution is a randomized algorithm for networks with expander topology. The algorithm succeeds with high probability and achieves a round complexity that is optimal up to a factor of the network’s mixing time and polylogarithmic terms. It leverages a multi-COBRA primitive, which uses multiple branching random walks running in parallel. A crucial aspect of our method is the use of these branching random walks to construct an optimal (up to a polylogarithmic factor) tree packing of a random graph, which is then used for efficient broadcasting. We also prove the problem to be NP-hard in a centralized setting and provide insights into why lower bounds that can be matched in expanders, namely graph diameter and |M|/minCut, cannot be tight in general graphs.
Cite as

Anton Paramonov and Roger Wattenhofer. Broadcast in Almost Mixing Time. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 71:1-71:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{paramonov_et_al:LIPIcs.STACS.2026.71,
  author =	{Paramonov, Anton and Wattenhofer, Roger},
  title =	{{Broadcast in Almost Mixing Time}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{71:1--71:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.71},
  URN =		{urn:nbn:de:0030-drops-255603},
  doi =		{10.4230/LIPIcs.STACS.2026.71},
  annote =	{Keywords: Distributed algorithms, Expander Graphs, Random graphs, Broadcast, Branching random walks, Tree packing, CONGEST model}
}
Document
DOI: 10.4230/LIPIcs.AofA.2024.20
Multicoloured Hardcore Model: Fast Mixing and Its Applications as a Scheduling Algorithm

Authors: Sam Olesker-Taylor

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract
In the hardcore model, certain vertices in a graph are active: the active vertices must form an independent set. We extend this to a multicoloured version: instead of simply being active or not, the active vertices are assigned a colour; active vertices of the same colour must not be adjacent. This models a scenario in which two neighbouring resources may interfere when active - eg, short-range radio communication. However, there are multiple channels (colours) available; they only interfere if both use the same channel. Other applications include routing in fibreoptic networks. We analyse Glauber dynamics. Vertices update their status at random times, at which a uniform colour is proposed: the vertex is assigned that colour if it is available; otherwise, it is set inactive. We find conditions for fast mixing of these dynamics. We also use them to model a queueing system: vertices only serve customers in their queue whilst active. The mixing estimates are applied to establish positive recurrence of the queue lengths, and bound their expectation in equilibrium.
Cite as

Sam Olesker-Taylor. Multicoloured Hardcore Model: Fast Mixing and Its Applications as a Scheduling Algorithm. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{oleskertaylor:LIPIcs.AofA.2024.20,
  author =	{Olesker-Taylor, Sam},
  title =	{{Multicoloured Hardcore Model: Fast Mixing and Its Applications as a Scheduling Algorithm}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{20:1--20:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.20},
  URN =		{urn:nbn:de:0030-drops-204558},
  doi =		{10.4230/LIPIcs.AofA.2024.20},
  annote =	{Keywords: mixing time, queueing theory, hardcore model, proper colourings, independent set, data transmission, randomised algorithms, routing, scheduling, multihop wireless networks}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.109
Geometric Bounds on the Fastest Mixing Markov Chain

Authors: Sam Olesker-Taylor and Luca Zanetti

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
In the Fastest Mixing Markov Chain problem, we are given a graph G = (V, E) and desire the discrete-time Markov chain with smallest mixing time τ subject to having equilibrium distribution uniform on V and non-zero transition probabilities only across edges of the graph [Boyd et al., 2004]. It is well-known that the mixing time τ_RW of the lazy random walk on G is characterised by the edge conductance Φ of G via Cheeger’s inequality: Φ^{-1} ≲ τ_RW ≲ Φ^{-2} log|V|. Edge conductance, however, fails to characterise the fastest mixing time τ^⋆ of G. Take, for example, a graph consisting of two n-vertex cliques connected by a perfect matching: its edge conductance is Θ(1/n), while τ^⋆ can be shown to be O(log n). We show, instead, that is possible to characterise the fastest mixing time τ^⋆ via a Cheeger-type inequality but for a different geometric quantity, namely the vertex conductance Ψ of G: Ψ^{-1} ≲ τ^* ≲ Ψ^{-2}(log|V|)^2. We prove this result by first relating vertex conductance to a new expansion measure, which we call matching conductance. We then relate matching conductance to a variational characterisation of τ^⋆ (or, more precisely, of the fastest relaxation time) due to Roch [Roch, 2005]. This is done by interpreting Roch’s characterisation as a particular instance of fractional vertex cover, which is dual to fractional matching. We believe matching conductance to be of independent interest and might have further applications in studying connectivity properties of graphs. This characterisation forbids fast mixing for graphs with small vertex conductance. To bypass this fundamental barrier, we consider Markov chains on G with equilibrium distribution which need not be uniform, but rather only ε-close to uniform in total variation. We call such chains almost mixing. We show that it is always possible to construct an almost mixing chain with mixing time τ ≲ ε^{-1} (diam G)² log |V|. Our proof is based on carefully constructing a reweighted spanning tree of G with good expansion properties and superimposing it over a simple "base" chain. In summary, our work together with known results shows that three fundamental geometric quantities characterise the mixing time on a graph according to three different notions of mixing: edge conductance characterises the mixing time of the lazy random walk, vertex conductance the fastest mixing time, while the diameter characterises the almost mixing time. Finally, we also discuss analogous questions for continuous-time and time-inhomogeneous chains.
Cite as

Sam Olesker-Taylor and Luca Zanetti. Geometric Bounds on the Fastest Mixing Markov Chain. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, p. 109:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{oleskertaylor_et_al:LIPIcs.ITCS.2022.109,
  author =	{Olesker-Taylor, Sam and Zanetti, Luca},
  title =	{{Geometric Bounds on the Fastest Mixing Markov Chain}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{109:1--109:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.109},
  URN =		{urn:nbn:de:0030-drops-157051},
  doi =		{10.4230/LIPIcs.ITCS.2022.109},
  annote =	{Keywords: mixing time, random walks, conductance, fastest mixing Markov chain}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.71
Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem

Authors: Huan Li, He Sun, and Luca Zanetti

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
We study spectral approaches for the MAX-2-LIN(k) problem, in which we are given a system of m linear equations of the form x_i - x_j is equivalent to c_{ij} mod k, and required to find an assignment to the n variables {x_i} that maximises the total number of satisfied equations. We consider Hermitian Laplacians related to this problem, and prove a Cheeger inequality that relates the smallest eigenvalue of a Hermitian Laplacian to the maximum number of satisfied equations of a MAX-2-LIN(k) instance I. We develop an O~(kn^2) time algorithm that, for any (1-epsilon)-satisfiable instance, produces an assignment satisfying a (1 - O(k)sqrt{epsilon})-fraction of equations. We also present a subquadratic-time algorithm that, when the graph associated with I is an expander, produces an assignment satisfying a (1- O(k^2)epsilon)-fraction of the equations. Our Cheeger inequality and first algorithm can be seen as generalisations of the Cheeger inequality and algorithm for MAX-CUT developed by Trevisan.
Cite as

Huan Li, He Sun, and Luca Zanetti. Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 71:1-71:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.ESA.2019.71,
  author =	{Li, Huan and Sun, He and Zanetti, Luca},
  title =	{{Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{71:1--71:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.71},
  URN =		{urn:nbn:de:0030-drops-111926},
  doi =		{10.4230/LIPIcs.ESA.2019.71},
  annote =	{Keywords: Spectral methods, Hermitian Laplacians, the Max-2-Lin problem, Unique Games}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.93
Random Walks on Dynamic Graphs: Mixing Times, Hitting Times, and Return Probabilities

Authors: Thomas Sauerwald and Luca Zanetti

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
We establish and generalise several bounds for various random walk quantities including the mixing time and the maximum hitting time. Unlike previous analyses, our derivations are based on rather intuitive notions of local expansion properties which allow us to capture the progress the random walk makes through t-step probabilities. We apply our framework to dynamically changing graphs, where the set of vertices is fixed while the set of edges changes in each round. For random walks on dynamic connected graphs for which the stationary distribution does not change over time, we show that their behaviour is in a certain sense similar to static graphs. For example, we show that the mixing and hitting times of any sequence of d-regular connected graphs is O(n^2), generalising a well-known result for static graphs. We also provide refined bounds depending on the isoperimetric dimension of the graph, matching again known results for static graphs. Finally, we investigate properties of random walks on dynamic graphs that are not always connected: we relate their convergence to stationarity to the spectral properties of an average of transition matrices and provide some examples that demonstrate strong discrepancies between static and dynamic graphs.
Cite as

Thomas Sauerwald and Luca Zanetti. Random Walks on Dynamic Graphs: Mixing Times, Hitting Times, and Return Probabilities. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 93:1-93:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{sauerwald_et_al:LIPIcs.ICALP.2019.93,
  author =	{Sauerwald, Thomas and Zanetti, Luca},
  title =	{{Random Walks on Dynamic Graphs: Mixing Times, Hitting Times, and Return Probabilities}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{93:1--93:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.93},
  URN =		{urn:nbn:de:0030-drops-106696},
  doi =		{10.4230/LIPIcs.ICALP.2019.93},
  annote =	{Keywords: random walks, dynamic graphs, hitting times}
}
  • Refine by Type
  • 6 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2026
  • 1 2024
  • 1 2022
  • 2 2019

  • Refine by Author
  • 3 Zanetti, Luca
  • 2 Olesker-Taylor, Sam
  • 1 Forster, Sebastian
  • 1 Goranci, Gramoz
  • 1 Li, Huan
  • Show More...

  • Refine by Series/Journal
  • 6 LIPIcs

  • Refine by Classification
  • 2 Mathematics of computing → Spectra of graphs
  • 2 Theory of computation → Random walks and Markov chains
  • 1 Mathematics of computing → Probabilistic algorithms
  • 1 Mathematics of computing → Stochastic processes
  • 1 Theory of computation → Approximation algorithms analysis
  • Show More...

  • Refine by Keyword
  • 2 mixing time
  • 2 random walks
  • 1 (Directed) hypergraphs
  • 1 Branching random walks
  • 1 Broadcast
  • Show More...

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