research
∙
08/02/2023
Fast Coloring Despite Congested Relays
We provide a O(log^6 log n)-round randomized algorithm for distance-2 co...
share
research
∙
04/19/2023
Coloring Fast with Broadcasts
We present an O(log^3log n)-round distributed algorithm for the (Δ+1)-co...
research
∙
01/16/2023
A Distributed Palette Sparsification Theorem
Is fully decentralized graph streaming possible? We consider this questi...
research
∙
11/14/2022
Fast Distributed Brooks' Theorem
We give a randomized Δ-coloring algorithm in the LOCAL model that runs i...
research
∙
08/17/2022
Fast Distributed Vertex Splitting with Applications
We present polyloglog n-round randomized distributed algorithms to compu...
research
∙
05/28/2022
Overcoming Congestion in Distributed Coloring
We present a new technique to efficiently sample and communicate a large...
research
∙
12/01/2021
Near-Optimal Distributed Degree+1 Coloring
We present a new approach to randomized distributed graph coloring that ...
research
∙
05/10/2021
Ultrafast Distributed Coloring of High Degree Graphs
We give a new randomized distributed algorithm for the Δ+1-list coloring...
research
∙
02/08/2021
Superfast Coloring in CONGEST via Efficient Color Sampling
We present a procedure for efficiently sampling colors in the model. It...
research
∙
12/28/2020
Efficient Randomized Distributed Coloring in CONGEST
Distributed vertex coloring is one of the classic problems and probably ...
research
∙
12/17/2020
Query-Competitive Sorting with Uncertainty
We study the problem of sorting under incomplete information, when queri...
research
∙
10/07/2020
Query Minimization under Stochastic Uncertainty
We study problems with stochastic uncertainty information on intervals f...
research
∙
08/12/2020
Tight Bounds on Subexponential Time Approximation of Set Cover and Related Problems
We show that Set Cover on instances with N elements cannot be approximat...
research
∙
08/10/2020
Coloring Fast Without Learning Your Neighbors' Colors
We give an improved randomized CONGEST algorithm for distance-2 coloring...
research
∙
05/13/2020
Distance-2 Coloring in the CONGEST Model
We give efficient randomized and deterministic distributed algorithms fo...
research
∙
08/05/2019
The Capacity of Smartphone Peer-to-Peer Networks
We study three capacity problems in the mobile telephone model, a networ...
research
∙
06/28/2018
Effective Wireless Scheduling via Hypergraph Sketches
An overarching issue in resource management of wireless networks is asse...
research
∙
06/08/2018
Distributed Algorithms for Minimum Degree Spanning Trees
The minimum degree spanning tree (MDST) problem requires the constructio...
research
∙
03/12/2018
Spanning Trees With Edge Conflicts and Wireless Connectivity
We introduce the problem of finding a spanning tree along with a partiti...
research
∙
03/02/2018
Simple and Local Independent Set Approximation
We bound the performance guarantees that follow from Turán-like bounds f...
research
∙
12/08/2017