7 Search Results for "Trehan, Chhaya"

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.FSTTCS.2025.36
Hardness of Finding Kings and Strong Kings

Authors: Ziad Ismaili Alaoui and Nikhil Mande

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
A king in a directed graph is a vertex v such that every other vertex is reachable from v via a path of length at most 2. It is well known that every tournament (a complete graph where each edge has a direction) has at least one king. Our contributions in this work are: - We show that the query complexity of determining existence of a king in arbitrary n-vertex digraphs is Θ(n²). This is in stark contrast to the case where the input is a tournament, where Shen, Sheng, and Wu [SICOMP'03] showed that a king can be found in O(n^{3/2}) queries. - In an attempt to increase the "fairness" in the definition of tournament winners, Ho and Chang [IPL'03] defined a strong king to be a king k such that, for every v that dominates k, the number of length-2 paths from k to v is strictly larger than the number of length-2 paths from v to k. We show that the query complexity of finding a strong king in a tournament is Θ(n²). This answers a question of Biswas, Jayapaul, Raman, and Satti [DAM'22] in the negative. A key component in our proofs is the design of specific tournaments where every vertex is a king, and analyzing certain properties of these tournaments. We feel these constructions and properties are independently interesting and may lead to more interesting results about tournament solutions.
Cite as

Ziad Ismaili Alaoui and Nikhil Mande. Hardness of Finding Kings and Strong Kings. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 36:1-36:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ismailialaoui_et_al:LIPIcs.FSTTCS.2025.36,
  author =	{Ismaili Alaoui, Ziad and Mande, Nikhil},
  title =	{{Hardness of Finding Kings and Strong Kings}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{36:1--36:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.36},
  URN =		{urn:nbn:de:0030-drops-250856},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.36},
  annote =	{Keywords: Tournaments, kings, query complexity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.22
Constructing Long Paths in Graph Streams

Authors: Christian Konrad and Chhaya Trehan

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
In the graph stream model of computation, an algorithm processes the edges of an n-vertex input graph in one or more sequential passes while using a memory that is sublinear in the input size. The streaming model poses significant challenges for algorithmically constructing long paths. Many known algorithms that are tasked with extending an existing path as a subroutine require an entire pass over the input to add a single additional edge. This raises a fundamental question: Are multiple passes inherently necessary to construct paths of non-trivial lengths, or can a single pass suffice? To address this question, we systematically study the Longest Path problem in the one-pass streaming model. In this problem, given a desired approximation factor α, the objective is to compute a path of length at least lp(G)/α, where lp(G) is the length of a longest path in the input graph G. We study the problem in the insertion-only and the insertion-deletion streaming models, and we give algorithms as well as space lower bounds for both undirected and directed graphs. Our results are: 1) We show that for undirected graphs, in both the insertion-only and the insertion-deletion models, there are semi-streaming algorithms, i.e., algorithms that use space O(n poly log n), that compute a path of length at least d/3 with high probability, where d is the average degree of the input graph. These algorithms can also yield an α-approximation to Longest Path using space Õ(n²/α). 2) Next, we show that such a result cannot be achieved for directed graphs, even in the insertion-only model. We show that computing a (n^{1-o(1)})-approximation to Longest Path in directed graphs in the insertion-only model requires space Ω(n²). This result is in line with recent results that demonstrate that processing directed graphs is often significantly harder than undirected graphs in the streaming model. 3) We further complement our results with two additional lower bounds. First, we show that semi-streaming space is insufficient for small constant factor approximations to Longest Path for undirected graphs in the insertion-only model. Last, in undirected graphs in the insertion-deletion model, we show that computing an α-approximation requires space Ω(n²/α³).
Cite as

Christian Konrad and Chhaya Trehan. Constructing Long Paths in Graph Streams. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 22:1-22:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{konrad_et_al:LIPIcs.ESA.2025.22,
  author =	{Konrad, Christian and Trehan, Chhaya},
  title =	{{Constructing Long Paths in Graph Streams}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{22:1--22:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.22},
  URN =		{urn:nbn:de:0030-drops-244902},
  doi =		{10.4230/LIPIcs.ESA.2025.22},
  annote =	{Keywords: Longest Path Problem, Streaming Algorithms, One-way Two-party Communication Complexity}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.36
Distributed Branching Random Walks and Their Applications

Authors: Vijeth Aradhya, Seth Gilbert, and Thorsten Götte

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
In recent years, the explosion of big data and analytics has necessitated distributed storage and processing with several compute nodes (e.g., multiple datacenters). These nodes collaboratively perform parallel computation, where the data is typically partitioned across these nodes to ensure scalability, redundancy and load-balancing. But the nodes may not always be co-located; in many cases, they are part of a larger communication network. Since those nodes only need to communicate among themselves, a key challenge is to design efficient routes catered to that subnetwork. In this work, we initiate the study of distributed sampling and routing problems for subnetworks in any well-connected network. Given any network G = (V, E) with mixing time τ_mix, consider the canonical problem of permutation routing [Ghaffari, Kuhn and Su, PODC 2017] that aims to minimize both congestion and dilation of the routes, where the demands (i.e., set of source-terminal pairs) are such that each node sends or receives number of messages proportional to its degree. We show that the permutation routing problem, when demands are restricted to any subset S ⊆ V (i.e., subnetwork), can be solved in exp(O(√(log|S|))) ⋅ Õ(τ_mix) rounds (where Õ(⋅) hides polylogarithmic factors of |V|). This means that the running time depends subpolynomially on the subnetwork size (i.e., not on the entire network size). The ability to solve permutation routing efficiently immediately implies that a large class of parallel algorithms can be simulated efficiently on the subnetwork. As a prerequisite to constructing efficient routes, we design and analyze distributed branching random walks that distribute tokens started by the nodes in the subnetwork. At a high-level, these algorithms operate by always moving each token according to a (lazy) simple random walk, but also branching a token into multiple tokens at some specified intervals; ultimately, if a node starts a branching walk, with its id in a token, then by the end of execution, several tokens with its id would be randomly distributed among the nodes. As these random walks can be started by many nodes, a crucial challenge is to ensure low-congestion, which is a primary focus of this paper.
Cite as

Vijeth Aradhya, Seth Gilbert, and Thorsten Götte. Distributed Branching Random Walks and Their Applications. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 36:1-36:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{aradhya_et_al:LIPIcs.OPODIS.2024.36,
  author =	{Aradhya, Vijeth and Gilbert, Seth and G\"{o}tte, Thorsten},
  title =	{{Distributed Branching Random Walks and Their Applications}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{36:1--36:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.36},
  URN =		{urn:nbn:de:0030-drops-225723},
  doi =		{10.4230/LIPIcs.OPODIS.2024.36},
  annote =	{Keywords: Distributed Graph Algorithms, Random Walks, Permutation Routing}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2022.25
When You Come at the King You Best Not Miss

Authors: Oded Lachish, Felix Reidl, and Chhaya Trehan

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
A tournament is an orientation of a complete graph. We say that a vertex x in a tournament T controls another vertex y if there exists a directed path of length at most two from x to y. A vertex is called a king if it controls every vertex of the tournament. It is well known that every tournament has a king. We follow Shen, Sheng, and Wu [Jian Shen et al., 2003] in investigating the query complexity of finding a king, that is, the number of arcs in T one has to know in order to surely identify at least one vertex as a king. The aforementioned authors showed that one always has to query at least Ω(n^{4/3}) arcs and provided a strategy that queries at most O(n^{3/2}). While this upper bound has not yet been improved for the original problem, [Biswas et al., 2017] proved that with O(n^{4/3}) queries one can identify a semi-king, meaning a vertex which controls at least half of all vertices. Our contribution is a novel strategy which improves upon the number of controlled vertices: using O(n^{4/3} polylog n) queries, we can identify a (1/2+2/17)-king. To achieve this goal we use a novel structural result for tournaments.
Cite as

Oded Lachish, Felix Reidl, and Chhaya Trehan. When You Come at the King You Best Not Miss. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 25:1-25:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{lachish_et_al:LIPIcs.FSTTCS.2022.25,
  author =	{Lachish, Oded and Reidl, Felix and Trehan, Chhaya},
  title =	{{When You Come at the King You Best Not Miss}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{25:1--25:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.25},
  URN =		{urn:nbn:de:0030-drops-174177},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.25},
  annote =	{Keywords: Digraphs, tournaments, kings, query complexity}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.51
(1+ε)-Approximate Shortest Paths in Dynamic Streams

Authors: Michael Elkin and Chhaya Trehan

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

Abstract
Computing approximate shortest paths in the dynamic streaming setting is a fundamental challenge that has been intensively studied. Currently existing solutions for this problem either build a sparse multiplicative spanner of the input graph and compute shortest paths in the spanner offline, or compute an exact single source BFS tree. Solutions of the first type are doomed to incur a stretch-space tradeoff of 2κ-1 versus n^{1+1/κ}, for an integer parameter κ. (In fact, existing solutions also incur an extra factor of 1+ε in the stretch for weighted graphs, and an additional factor of log^{O(1)}n in the space.) The only existing solution of the second type uses n^{1/2 - O(1/κ)} passes over the stream (for space O(n^{1+1/κ})), and applies only to unweighted graphs. In this paper we show that (1+ε)-approximate single-source shortest paths can be computed with Õ(n^{1+1/κ}) space using just constantly many passes in unweighted graphs, and polylogarithmically many passes in weighted graphs. Moreover, the same result applies for multi-source shortest paths, as long as the number of sources is O(n^{1/κ}). We achieve these results by devising efficient dynamic streaming constructions of (1 + ε, β)-spanners and hopsets. On our way to these results, we also devise a new dynamic streaming algorithm for the 1-sparse recovery problem. Even though our algorithm for this task is slightly inferior to the existing algorithms of [S. Ganguly, 2007; Graham Cormode and D. Firmani, 2013], we believe that it is of independent interest.
Cite as

Michael Elkin and Chhaya Trehan. (1+ε)-Approximate Shortest Paths in Dynamic Streams. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 51:1-51:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{elkin_et_al:LIPIcs.APPROX/RANDOM.2022.51,
  author =	{Elkin, Michael and Trehan, Chhaya},
  title =	{{(1+\epsilon)-Approximate Shortest Paths in Dynamic Streams}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{51:1--51:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.51},
  URN =		{urn:nbn:de:0030-drops-171733},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.51},
  annote =	{Keywords: Shortest Paths, Dynamic Streams, Approximate Distances, Spanners, Hopsets}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.17
On the Termination of Flooding

Authors: Walter Hussak and Amitabh Trehan

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
Flooding is among the simplest and most fundamental of all graph/network algorithms. Consider a (distributed network in the form of a) finite undirected graph G with a distinguished node v that begins flooding by sending copies of the same message to all its neighbours and the neighbours, in the next round, forward the message to all and only the neighbours they did not receive the message from in that round and so on. We assume that nodes do not keep a record of the flooding event, thus, raising the possibility that messages may circulate infinitely even on a finite graph. We call this history-less process amnesiac flooding (to distinguish from a classic distributed implementation of flooding that maintains a history of received messages to ensure a node never sends the same message again). Flooding will terminate when no node in G sends a message in a round, and, thus, subsequent rounds. As far as we know, the question of termination for amnesiac flooding has not been settled - rather, non-termination is implicitly assumed. In this paper, we show that surprisingly synchronous amnesiac flooding always terminates on any arbitrary finite graph and derive exact termination times which differ sharply in bipartite and non-bipartite graphs. In particular, synchronous flooding terminates in e rounds, where e is the eccentricity of the source node, if and only if G is bipartite, and, otherwise, in j rounds where e < j ≤ e+d+1 and d is the diameter of G. Since e is bounded above by d, this implies termination times of at most d and of at most 2d + 1 for bipartite and non-bipartite graphs respectively. This suggests that if communication/broadcast to all nodes is the motivation, the history-less amnesiac flooding is asymptotically time optimal and obviates the need for construction and maintenance of spanning structures like spanning trees. Moreover, the clear separation in the termination times of bipartite and non-bipartite graphs may suggest possible mechanisms for distributed discovery of the topology/distances in an arbitrary graph. For comparison, we also show that, for asynchronous networks, however, an adversary can force the process to be non-terminating.
Cite as

Walter Hussak and Amitabh Trehan. On the Termination of Flooding. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 17:1-17:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{hussak_et_al:LIPIcs.STACS.2020.17,
  author =	{Hussak, Walter and Trehan, Amitabh},
  title =	{{On the Termination of Flooding}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{17:1--17:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.17},
  URN =		{urn:nbn:de:0030-drops-118786},
  doi =		{10.4230/LIPIcs.STACS.2020.17},
  annote =	{Keywords: Flooding algorithm, Network algorithms, Distributed algorithms, Graph theory, Termination, Bipartiteness, Communication, Broadcast}
}
  • Refine by Type
  • 7 Document/PDF
  • 4 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 3 2025
  • 2 2022
  • 1 2020

  • Refine by Author
  • 3 Trehan, Chhaya
  • 1 Aradhya, Vijeth
  • 1 Elkin, Michael
  • 1 Gilbert, Seth
  • 1 Götte, Thorsten
  • Show More...

  • Refine by Series/Journal
  • 7 LIPIcs

  • Refine by Classification
  • 3 Theory of computation → Distributed algorithms
  • 2 Mathematics of computing → Graph algorithms
  • 2 Theory of computation → Graph algorithms analysis
  • 2 Theory of computation → Random walks and Markov chains
  • 2 Theory of computation → Streaming models
  • Show More...

  • Refine by Keyword
  • 2 Broadcast
  • 2 Distributed algorithms
  • 2 kings
  • 2 query complexity
  • 1 Approximate Distances
  • 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