research
∙
07/15/2023
Fully Scalable MPC Algorithms for Clustering in High Dimension
We design new algorithms for k-clustering in high-dimensional Euclidean ...
share
research
∙
06/21/2023
Optimal (degree+1)-Coloring in Congested Clique
We consider the distributed complexity of the (degree+1)-list coloring p...
research
∙
04/12/2023
On Parallel k-Center Clustering
We consider the classic k-center problem in a parallel setting, on the l...
research
∙
02/08/2023
Fast Parallel Degree+1 List Coloring
Graph coloring problems are arguably among the most fundamental graph pr...
research
∙
10/11/2022
Routing Schemes for Hybrid Communication Networks in Unit-Disk Graphs
Hybrid communication networks provide multiple modes of communication wi...
research
∙
04/05/2022
Streaming Facility Location in High Dimension via New Geometric Hashing
In Euclidean Uniform Facility Location, the input is a set of clients in...
research
∙
02/16/2022
Near-Shortest Path Routing in Hybrid Communication Networks
Hybrid networks, i.e., networks that leverage different means of communi...
research
∙
12/10/2021
Improved Deterministic (Δ+1)-Coloring in Low-Space MPC
We present a deterministic O(logloglog n)-round low-space Massively Para...
research
∙
08/26/2021
On Truly Parallel Time in Population Protocols
The parallel time of a population protocol is defined as the average num...
research
∙
08/09/2021
Deterministic Massively Parallel Connectivity
We consider the problem of designing fundamental graph algorithms on the...
research
∙
06/03/2021
Component Stability in Low-Space Massively Parallel Computation
We study the power and limitations of component-stable algorithms in the...
research
∙
11/09/2020
Streaming Algorithms for Geometric Steiner Forest
We consider a natural generalization of the Steiner tree problem, the St...
research
∙
09/13/2020
Simple, Deterministic, Constant-Round Coloring in the Congested Clique
We settle the complexity of the (Δ+1)-coloring and (Δ+1)-list coloring p...
research
∙
08/26/2020
Combinatorial Communication in the Locker Room
The reader may be familiar with various problems involving prisoners and...
research
∙
12/11/2019
Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space
The Massively Parallel Computation (MPC) model is an emerging model whic...
research
∙
09/23/2019
A characterization of graph properties testable for general planar graphs with one-sided error (It is all about forbidden subgraphs)
The problem of characterizing testable graph properties (properties that...
research
∙
05/05/2019
Testable Properties in General Graphs and Random Order Streaming
We present a novel framework closely linking the areas of property testi...
research
∙
07/10/2018
Online Facility Location with Deletions
In this paper we study three previously unstudied variants of the online...
research
∙
07/03/2018
Detecting cliques in CONGEST networks
The problem of detecting network structures plays a central role in dist...
research
∙
05/13/2018
Randomized Communication Without Network Knowledge
Radio networks are a long-studied model for distributed system of device...
research
∙
05/13/2018