11 Search Results for "Dani, Varsha"

Document
DOI: 10.4230/LIPIcs.OPODIS.2025.15
Time-Optimal and Energy-Efficient Deterministic Consensus

Authors: Shachar Meir, Hugo Mirault, David Peleg, and Peter Robinson

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract
We study fault-tolerant consensus in a variant of the synchronous message passing model, where, in each round, every node can choose to be awake or asleep. This is known as the sleeping model (Chatterjee, Gmyr, Pandurangan PODC 2020) and defines the awake complexity (also called energy complexity), which measures the maximum number of rounds that any node is awake throughout the execution. Only awake nodes can send and receive messages in a given round and all messages sent to sleeping nodes are lost. We present new deterministic consensus algorithms that tolerate up to f < n crash failures, where n is the number of nodes. Our algorithms match the optimal time complexity lower bound of f+1 rounds. For multi-value consensus, where the input values are chosen from some possibly large set, we achieve an energy complexity of 𝒪(⌈ f² / n ⌉) rounds, whereas for binary consensus, we show an algorithm to achieve 𝒪(⌈ f / √n ⌉) energy complexity.
Cite as

Shachar Meir, Hugo Mirault, David Peleg, and Peter Robinson. Time-Optimal and Energy-Efficient Deterministic Consensus. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{meir_et_al:LIPIcs.OPODIS.2025.15,
  author =	{Meir, Shachar and Mirault, Hugo and Peleg, David and Robinson, Peter},
  title =	{{Time-Optimal and Energy-Efficient Deterministic Consensus}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.15},
  URN =		{urn:nbn:de:0030-drops-251881},
  doi =		{10.4230/LIPIcs.OPODIS.2025.15},
  annote =	{Keywords: Distributed computing, Crash faults, Consensus, Energy complexity, Sleeping model}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.14
Energy-Efficient Maximal Independent Sets in Radio Networks

Authors: Dominick Banasik, Varsha Dani, Fabien Dufoulon, Aayush Gupta, Thomas P. Hayes, and Gopal Pandurangan

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
The maximal independent set (MIS) is one of the most fundamental problems in distributed computing, and it has been studied intensively for over four decades. This paper focuses on the MIS problem in the radio network model, a standard model widely used to model wireless networks, particularly ad hoc wireless and sensor networks. Energy is a premium resource in these networks, which are typically battery-powered. Hence, designing distributed algorithms that use as little energy as possible is crucial. We use the well-established energy model where a node can be sleeping or awake in a round, and only the awake rounds (when it can send or listen) determine the energy complexity of the algorithm, which we want to minimize. We present new, more energy-efficient MIS algorithms in radio networks with arbitrary and unknown graph topology. We present algorithms for two popular variants of the radio model - with collision detection (CD) and without collision detection (no-CD). Specifically, we obtain the following results: 1) CD model: We present a randomized distributed MIS algorithm with energy complexity O(log n), round complexity O(log² n), and failure probability 1 / poly(n), where n is the network size. We show that our energy complexity is optimal by showing a matching Ω(log n) lower bound. 2) no-CD model: In the more challenging no-CD model, we present a randomized distributed MIS algorithm with energy complexity O(log²n log log n), round complexity O(log³ n log Δ), and failure probability 1 / poly(n). The energy complexity of our algorithm is significantly lower than the round (and energy) complexity of O(log³ n) of the best known distributed MIS algorithm of Davies [PODC 2023] for arbitrary graph topology.
Cite as

Dominick Banasik, Varsha Dani, Fabien Dufoulon, Aayush Gupta, Thomas P. Hayes, and Gopal Pandurangan. Energy-Efficient Maximal Independent Sets in Radio Networks. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 14:1-14:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{banasik_et_al:LIPIcs.DISC.2025.14,
  author =	{Banasik, Dominick and Dani, Varsha and Dufoulon, Fabien and Gupta, Aayush and Hayes, Thomas P. and Pandurangan, Gopal},
  title =	{{Energy-Efficient Maximal Independent Sets in Radio Networks}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{14:1--14:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.14},
  URN =		{urn:nbn:de:0030-drops-248311},
  doi =		{10.4230/LIPIcs.DISC.2025.14},
  annote =	{Keywords: Distributed Computing, Energy Complexity, Sleeping Model, Radio Networks, Maximal Independent Set}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2025.47
Brief Announcement: Highly Dynamic and Fully Distributed Data Structures

Authors: John Augustine, Antonio Cruciani, and Iqra Altaf Gillani

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
We study robust and efficient distributed algorithms for building and maintaining distributed data structures in dynamic Peer-to-Peer (P2P) networks. P2P networks are characterized by a high level of dynamicity with abrupt heavy node churn (nodes that join and leave the network continuously over time). We present a novel algorithmic framework to build and maintain, with high probability, a skip list for poly(n) rounds despite a churn rate of 𝒪(n/log n), which is the number of nodes joining and/or leaving per round; n is the stable network size. We assume that the churn is controlled by an oblivious adversary that has complete knowledge and control of what nodes join and leave and at what time and has unlimited computational power, but is oblivious to the random choices made by the algorithm. Importantly, the maintenance overhead in any interval of time (measured in terms of the total number of messages exchanged and the number of edges formed/deleted) is (up to log factors) proportional to the churn rate. Furthermore, the algorithm is scalable in that the messages are small (i.e., at most polylog(n) bits) and every node sends and receives at most polylog(n) messages per round. To the best of our knowledge, our work provides the first-known fully-distributed data structure and associated algorithms that provably work under highly dynamic settings (i.e., high churn rate that is near-linear in n). Furthermore, the nodes operate in a localized manner. Our framework crucially relies on new distributed and parallel algorithms to merge two n-element skip lists and delete a large subset of items, both in 𝒪(log n) rounds with high probability. These procedures may be of independent interest due to their elegance and potential applicability in other contexts in distributed data structures. Finally, we believe that our framework can be generalized to other distributed and dynamic data structures including graphs, potentially leading to stable distributed computation despite heavy churn.
Cite as

John Augustine, Antonio Cruciani, and Iqra Altaf Gillani. Brief Announcement: Highly Dynamic and Fully Distributed Data Structures. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 47:1-47:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{augustine_et_al:LIPIcs.DISC.2025.47,
  author =	{Augustine, John and Cruciani, Antonio and Gillani, Iqra Altaf},
  title =	{{Brief Announcement: Highly Dynamic and Fully Distributed Data Structures}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{47:1--47:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.47},
  URN =		{urn:nbn:de:0030-drops-248636},
  doi =		{10.4230/LIPIcs.DISC.2025.47},
  annote =	{Keywords: Peer-to-peer network, dynamic network, data structure, churn, distributed algorithm, randomized algorithm}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.98
The Long Arm of Nashian Allocation in Online p-Mean Welfare Maximization

Authors: Zhiyi Huang, Chui Shan Lee, Xinkai Shu, and Zhaozi Wang

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We study the online allocation of divisible items to n agents with additive valuations for p-mean welfare maximization, a problem introduced by Barman, Khan, and Maiti (2022). Our algorithmic and hardness results characterize the optimal competitive ratios for the entire spectrum of -∞ ≤ p ≤ 1. Surprisingly, our improved algorithms for all p ≤ (1)/(log n) are simply the greedy algorithm for the Nash welfare, supplemented with two auxiliary components to ensure all agents have non-zero utilities and to help a small number of agents with low utilities. In this sense, the long arm of Nashian allocation achieves near-optimal competitive ratios not only for Nash welfare but also all the way to egalitarian welfare.
Cite as

Zhiyi Huang, Chui Shan Lee, Xinkai Shu, and Zhaozi Wang. The Long Arm of Nashian Allocation in Online p-Mean Welfare Maximization. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 98:1-98:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.ICALP.2025.98,
  author =	{Huang, Zhiyi and Lee, Chui Shan and Shu, Xinkai and Wang, Zhaozi},
  title =	{{The Long Arm of Nashian Allocation in Online p-Mean Welfare Maximization}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{98:1--98:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l 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.2025.98},
  URN =		{urn:nbn:de:0030-drops-234754},
  doi =		{10.4230/LIPIcs.ICALP.2025.98},
  annote =	{Keywords: Online Algorithms, Fair Division, Nash Welfare}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.59
Error Correction for Message Streams

Authors: Meghal Gupta and Rachel Yun Zhang

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
In the setting of error correcting codes, Alice wants to send a message x ∈ {0,1}ⁿ to Bob via an encoding enc(x) that is resilient to error. In this work, we investigate the scenario where Bob is a low space decoder. More precisely, he receives Alice’s encoding enc(x) bit-by-bit and desires to compute some function f(x) in low space. A generic error-correcting code does not accomplish this because decoding is a very global process and requires at least linear space. Locally decodable codes partially solve this problem as they allow Bob to learn a given bit of x in low space, but not compute a generic function f. Our main result is an encoding and decoding procedure where Bob is still able to compute any such function f in low space when a constant fraction of the stream is corrupted. More precisely, we describe an encoding function enc(x) of length poly(n) so that for any decoder (streaming algorithm) A that on input x computes f(x) in space s, there is an explicit decoder B that computes f(x) in space s ⋅ polylog(n) as long as there were not more than 1/4 - ε fraction of (adversarial) errors in the input stream enc(x).
Cite as

Meghal Gupta and Rachel Yun Zhang. Error Correction for Message Streams. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 59:1-59:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gupta_et_al:LIPIcs.ITCS.2025.59,
  author =	{Gupta, Meghal and Zhang, Rachel Yun},
  title =	{{Error Correction for Message Streams}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{59:1--59:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.59},
  URN =		{urn:nbn:de:0030-drops-226875},
  doi =		{10.4230/LIPIcs.ITCS.2025.59},
  annote =	{Keywords: error-correcting codes, streaming algorithms, space-efficient algorithms}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.26
The Singular Optimality of Distributed Computation in LOCAL

Authors: Fabien Dufoulon, Gopal Pandurangan, Peter Robinson, and Michele Scquizzato

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

Abstract
It has been shown that one can design distributed algorithms that are (nearly) singularly optimal, meaning they simultaneously achieve optimal time and message complexity (within polylogarithmic factors), for several fundamental global problems such as broadcast, leader election, and spanning tree construction, under the KT₀ assumption. With this assumption, nodes have initial knowledge only of themselves, not their neighbors. In this case the time and message lower bounds are Ω(D) and Ω(m), respectively, where D is the diameter of the network and m is the number of edges, and there exist (even) deterministic algorithms that simultaneously match these bounds. On the other hand, under the KT₁ assumption, whereby each node has initial knowledge of itself and the identifiers of its neighbors, the situation is not clear. For the KT₁ CONGEST model (where messages are of small size), King, Kutten, and Thorup (KKT) showed that one can solve several fundamental global problems (with the notable exception of BFS tree construction) such as broadcast, leader election, and spanning tree construction with Õ(n) message complexity (n is the network size), which can be significantly smaller than m. Randomization is crucial in obtaining this result. While the message complexity of the KKT result is near-optimal, its time complexity is Õ(n) rounds, which is far from the standard lower bound of Ω(D). An important open question is whether one can achieve singular optimality for the above problems in the KT₁ CONGEST model, i.e., whether there exists an algorithm running in Õ(D) rounds and Õ(n) messages. Another important and related question is whether the fundamental BFS tree construction can be solved with Õ(n) messages (regardless of the number of rounds as long as it is polynomial in n) in KT₁. In this paper, we show that in the KT₁ LOCAL model (where message sizes are not restricted), singular optimality is achievable. Our main result is that all global problems, including BFS tree construction, can be solved in Õ(D) rounds and Õ(n) messages, where both bounds are optimal up to polylogarithmic factors. Moreover, we show that this can be achieved deterministically.
Cite as

Fabien Dufoulon, Gopal Pandurangan, Peter Robinson, and Michele Scquizzato. The Singular Optimality of Distributed Computation in LOCAL. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dufoulon_et_al:LIPIcs.OPODIS.2024.26,
  author =	{Dufoulon, Fabien and Pandurangan, Gopal and Robinson, Peter and Scquizzato, Michele},
  title =	{{The Singular Optimality of Distributed Computation in LOCAL}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{26:1--26:17},
  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.26},
  URN =		{urn:nbn:de:0030-drops-225629},
  doi =		{10.4230/LIPIcs.OPODIS.2024.26},
  annote =	{Keywords: Distributed algorithms, round and message complexity, BFS tree construction, leader election}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2024.36
Fraud Detection for Random Walks

Authors: Varsha Dani, Thomas P. Hayes, Seth Pettie, and Jared Saia

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
Traditional fraud detection is often based on finding statistical anomalies in data sets and transaction histories. A sophisticated fraudster, aware of the exact kinds of tests being deployed, might be difficult or impossible to catch. We are interested in paradigms for fraud detection that are provably robust against any adversary, no matter how sophisticated. In other words, the detection strategy should rely on signals in the data that are inherent in the goals the adversary is trying to achieve. Specifically, we consider a fraud detection game centered on a random walk on a graph. We assume this random walk is implemented by having a player at each vertex, who can be honest or not. In particular, when the random walk reaches a vertex owned by an honest player, it proceeds to a uniformly random neighbor at the next timestep. However, when the random walk reaches a dishonest player, it instead proceeds to an arbitrary neighbor chosen by an omniscient Adversary. The game is played between the Adversary and a Referee who sees the trajectory of the random walk. At any point during the random walk, if the Referee determines that a {specific} vertex is controlled by a dishonest player, the Referee accuses that player, and therefore wins the game. The Referee is allowed to make the occasional incorrect accusation, but must follow a policy that makes such mistakes with small probability of error. The goal of the adversary is to make the cover time large, ideally infinite, i.e., the walk should never reach at least one vertex. We consider the following basic question: how much can the omniscient Adversary delay the cover time without getting caught? Our main result is a tight upper bound on this delay factor. We also discuss possible applications of our results to settings such as Rotor Walks, Leader Election, and Sybil Defense.
Cite as

Varsha Dani, Thomas P. Hayes, Seth Pettie, and Jared Saia. Fraud Detection for Random Walks. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 36:1-36:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dani_et_al:LIPIcs.ITCS.2024.36,
  author =	{Dani, Varsha and Hayes, Thomas P. and Pettie, Seth and Saia, Jared},
  title =	{{Fraud Detection for Random Walks}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{36:1--36:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.36},
  URN =		{urn:nbn:de:0030-drops-195645},
  doi =		{10.4230/LIPIcs.ITCS.2024.36},
  annote =	{Keywords: Fraud detection, random processes, Markov chains}
}
Document
DOI: 10.4230/LIPIcs.DISC.2022.16
How to Wake up Your Neighbors: Safe and Nearly Optimal Generic Energy Conservation in Radio Networks

Authors: Varsha Dani and Thomas P. Hayes

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
Recent work [Chang et al., 2018; Chang et al., 2020; Varsha Dani et al., 2021] has shown that it is sometimes feasible to significantly reduce the energy usage of some radio-network algorithms by adaptively powering down the radio receiver when it is not needed. Although past work has focused on modifying specific network algorithms in this way, we now ask the question of whether this problem can be solved in a generic way, treating the algorithm as a kind of black box. We are able to answer this question in the affirmative, presenting a new general way to modify arbitrary radio-network algorithms in an attempt to save energy. At the expense of a small increase in the time complexity, we can provably reduce the energy usage to an extent that is provably nearly optimal within a certain class of general-purpose algorithms. As an application, we show that our algorithm reduces the energy cost of breadth-first search in radio networks from the previous best bound of 2^O(√{log n}) to polylog(n), where n is the number of nodes in the network A key ingredient in our algorithm is hierarchical clustering based on additive Voronoi decomposition done at multiple scales. Similar clustering algorithms have been used in other recent work on energy-aware computation in radio networks, but we believe the specific approach presented here may be of independent interest.
Cite as

Varsha Dani and Thomas P. Hayes. How to Wake up Your Neighbors: Safe and Nearly Optimal Generic Energy Conservation in Radio Networks. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 16:1-16:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dani_et_al:LIPIcs.DISC.2022.16,
  author =	{Dani, Varsha and Hayes, Thomas P.},
  title =	{{How to Wake up Your Neighbors: Safe and Nearly Optimal Generic Energy Conservation in Radio Networks}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{16:1--16:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.16},
  URN =		{urn:nbn:de:0030-drops-172071},
  doi =		{10.4230/LIPIcs.DISC.2022.16},
  annote =	{Keywords: Radio Networks, Low Energy Computation, Clustering}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.48
Improved Reconstruction of Random Geometric Graphs

Authors: Varsha Dani, Josep Díaz, Thomas P. Hayes, and Cristopher Moore

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
Embedding graphs in a geographical or latent space, i.e. inferring locations for vertices in Euclidean space or on a smooth manifold or submanifold, is a common task in network analysis, statistical inference, and graph visualization. We consider the classic model of random geometric graphs where n points are scattered uniformly in a square of area n, and two points have an edge between them if and only if their Euclidean distance is less than r. The reconstruction problem then consists of inferring the vertex positions, up to the symmetries of the square, given only the adjacency matrix of the resulting graph. We give an algorithm that, if r = n^α for α > 0, with high probability reconstructs the vertex positions with a maximum error of O(n^β) where β = 1/2-(4/3)α, until α ≥ 3/8 where β = 0 and the error becomes O(√{log n}). This improves over earlier results, which were unable to reconstruct with error less than r. Our method estimates Euclidean distances using a hybrid of graph distances and short-range estimates based on the number of common neighbors. We extend our results to the surface of the sphere in ℝ³ and to hypercubes in any constant dimension.
Cite as

Varsha Dani, Josep Díaz, Thomas P. Hayes, and Cristopher Moore. Improved Reconstruction of Random Geometric Graphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 48:1-48:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dani_et_al:LIPIcs.ICALP.2022.48,
  author =	{Dani, Varsha and D{\'\i}az, Josep and Hayes, Thomas P. and Moore, Cristopher},
  title =	{{Improved Reconstruction of Random Geometric Graphs}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{48:1--48:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.48},
  URN =		{urn:nbn:de:0030-drops-163897},
  doi =		{10.4230/LIPIcs.ICALP.2022.48},
  annote =	{Keywords: Reconstruction algorithm, distances in RGG, d-dimensional hypercube, 3 dimensional sphere}
}
Document
DOI: 10.4230/LIPIcs.DISC.2021.19
Wake up and Join Me! an Energy-Efficient Algorithm for Maximal Matching in Radio Networks

Authors: Varsha Dani, Aayush Gupta, Thomas P. Hayes, and Seth Pettie

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
We consider networks of small, autonomous devices that communicate with each other wirelessly. Minimizing energy usage is an important consideration in designing algorithms for such networks, as battery life is a crucial and limited resource. Working in a model where both sending and listening for messages deplete energy, we consider the problem of finding a maximal matching of the nodes in a radio network of arbitrary and unknown topology. We present a distributed randomized algorithm that produces, with high probability, a maximal matching. The maximum energy cost per node is O(log² n), and the time complexity is O(Δ log n). Here n is any upper bound on the number of nodes, and Δ is any upper bound on the maximum degree; n and Δ are parameters of our algorithm that we assume are known a priori to all the processors. We note that there exist families of graphs for which our bounds on energy cost and time complexity are simultaneously optimal up to polylog factors, so any significant improvement would need additional assumptions about the network topology. We also consider the related problem of assigning, for each node in the network, a neighbor to back up its data in case of eventual node failure. Here, a key goal is to minimize the maximum load, defined as the number of nodes assigned to a single node. We present an efficient decentralized low-energy algorithm that finds a neighbor assignment whose maximum load is at most a polylog(n) factor bigger that the optimum.
Cite as

Varsha Dani, Aayush Gupta, Thomas P. Hayes, and Seth Pettie. Wake up and Join Me! an Energy-Efficient Algorithm for Maximal Matching in Radio Networks. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{dani_et_al:LIPIcs.DISC.2021.19,
  author =	{Dani, Varsha and Gupta, Aayush and Hayes, Thomas P. and Pettie, Seth},
  title =	{{Wake up and Join Me! an Energy-Efficient Algorithm for Maximal Matching in Radio Networks}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.19},
  URN =		{urn:nbn:de:0030-drops-148219},
  doi =		{10.4230/LIPIcs.DISC.2021.19},
  annote =	{Keywords: Distributed Algorithms, Energy-Aware Computation, Radio Networks, Maximal Matching, Sensor Networks}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.59
On the Power of Choice for k-Colorability of Random Graphs

Authors: Varsha Dani, Diksha Gupta, and Thomas P. Hayes

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

Abstract
In an r-choice Achlioptas process, random edges are generated r at a time, and an online strategy is used to select one of them for inclusion in a graph. We investigate the problem of whether such a selection strategy can shift the k-colorability transition; that is, the number of edges at which the graph goes from being k-colorable to non-k-colorable. We show that, for k ≥ 9, two choices suffice to delay the k-colorability threshold, and that for every k ≥ 2, six choices suffice.
Cite as

Varsha Dani, Diksha Gupta, and Thomas P. Hayes. On the Power of Choice for k-Colorability of Random Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 59:1-59:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{dani_et_al:LIPIcs.APPROX/RANDOM.2021.59,
  author =	{Dani, Varsha and Gupta, Diksha and Hayes, Thomas P.},
  title =	{{On the Power of Choice for k-Colorability of Random Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{59:1--59:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.59},
  URN =		{urn:nbn:de:0030-drops-147527},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.59},
  annote =	{Keywords: Random graphs, Achlioptas Processes, Phase Transition, Graph Colorability}
}
  • Refine by Type
  • 11 Document/PDF
  • 6 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 5 2025
  • 1 2024
  • 2 2022
  • 2 2021

  • Refine by Author
  • 6 Dani, Varsha
  • 6 Hayes, Thomas P.
  • 2 Dufoulon, Fabien
  • 2 Gupta, Aayush
  • 2 Pandurangan, Gopal
  • Show More...

  • Refine by Series/Journal
  • 11 LIPIcs

  • Refine by Classification
  • 5 Theory of computation → Distributed algorithms
  • 1 Mathematics of computing → Coding theory
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Mathematics of computing → Probabilistic algorithms
  • 1 Mathematics of computing → Probability and statistics
  • Show More...

  • Refine by Keyword
  • 3 Radio Networks
  • 1 3 dimensional sphere
  • 1 Achlioptas Processes
  • 1 BFS tree construction
  • 1 Clustering
  • 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