research
∙
05/02/2023
The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs
In this paper, we present a low-diameter decomposition algorithm in the ...
share
research
∙
04/30/2023
Ortho-Radial Drawing in Near-Linear Time
An orthogonal drawing is an embedding of a plane graph into a grid. In a...
research
∙
04/15/2023
Fully Scalable Massively Parallel Algorithms for Embedded Planar Graphs
We consider the massively parallel computation (MPC) model, which is a t...
research
∙
04/13/2023
Universally Optimal Deterministic Broadcasting in the HYBRID Distributed Model
In theoretical computer science, it is a common practice to show existen...
research
∙
04/10/2023
Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications
In the LOCAL model, low-diameter decomposition is a useful tool in desig...
research
∙
05/17/2022
The Energy Complexity of Las Vegas Leader Election
We consider the time and energy complexities of randomized leader electi...
research
∙
05/17/2022
Narrowing the LOCALx2013CONGEST Gaps in Sparse Networks via Expander Decompositions
Many combinatorial optimization problems can be approximated within (1 ±...
research
∙
04/20/2022
Deterministic Distributed algorithms and Descriptive Combinatorics on Δ-regular trees
We study complexity classes of local problems on regular trees from the ...
research
∙
02/17/2022
Efficient Classification of Local Problems in Regular Trees
We give practical, efficient algorithms that automatically determine the...
research
∙
11/05/2021
On Homomorphism Graphs
We introduce a new type of examples of bounded degree acyclic Borel grap...
research
∙
06/03/2021
Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics
We study connections between distributed local algorithms, finitary fact...
research
∙
05/16/2021
Near-Optimal Time-Energy Trade-Offs for Deterministic Leader Election
We consider the energy complexity of the leader election problem in the ...
research
∙
02/19/2021
Strong-Diameter Network Decomposition
Network decomposition is a central concept in the study of distributed g...
research
∙
11/14/2020
Tight Distributed Listing of Cliques
Much progress has recently been made in understanding the complexity lan...
research
∙
09/21/2020
The Complexity Landscape of Distributed Locally Checkable Problems on Trees
Recent research revealed the existence of gaps in the complexity landsca...
research
∙
07/29/2020
Deterministic Distributed Expander Decomposition and Routing with Applications in Distributed Derandomization
There is a recent exciting line of work in distributed graph algorithms ...
research
∙
07/19/2020
The Energy Complexity of BFS in Radio Networks
We consider a model of energy complexity in Radio Networks in which tran...
research
∙
02/18/2020
Distributed graph problems through an automata-theoretic lens
We study the following algorithm synthesis question: given the descripti...
research
∙
01/21/2020
Streaming Complexity of Spanning Tree Computation
The semi-streaming model is a variant of the streaming model frequently ...
research
∙
04/17/2019
Improved Distributed Expander Decomposition and Nearly Optimal Triangle Enumeration
An (ϵ,ϕ)-expander decomposition of a graph G=(V,E) is a clustering of th...
research
∙
11/05/2018
The distributed complexity of locally checkable problems on paths is decidable
Consider a computer network that consists of a path with n nodes. The no...
research
∙
07/17/2018
Distributed Triangle Detection via Expander Decomposition
We present improved distributed algorithms for triangle detection and it...
research
∙
05/10/2018
Energy Complexity of Distance Computation in Multi-hop Networks
Energy efficiency is a critical issue for wireless devices operated unde...
research
∙
11/03/2017