research
∙
04/02/2023
Mini-batch k-means terminates within O(d/ε) iterations
We answer the question: "Does local progress (on batches) imply global p...
share
research
∙
05/30/2022
Fully Polynomial-Time Distributed Computation in Low-Treewidth Graphs
We consider global problems, i.e. problems that take at least diameter t...
research
∙
04/29/2022
FRANCIS: Fast Reaction Algorithms for Network Coordination In Switches
Distributed protocols are widely used to support network functions such ...
research
∙
11/10/2021
SGD Through the Lens of Kolmogorov Complexity
We prove that stochastic gradient descent (SGD) finds a solution that ac...
research
∙
05/27/2021
On the Complexity of Load Balancing in Dynamic Networks
In the load balancing problem, each node in a network is assigned a load...
research
∙
05/25/2021
Smoothed Analysis of Population Protocols
In this work, we initiate the study of smoothed analysis of population p...
research
∙
09/28/2020
Models of Smoothing in Dynamic Networks
Smoothed analysis is a framework suggested for mediating gaps between wo...
research
∙
09/17/2020
Finding Subgraphs in Highly Dynamic Networks
In this paper we consider the fundamental problem of finding subgraphs i...
research
∙
06/27/2019
Improved Distributed Approximation to Maximum Independent Set
We present improved results for approximating Maximum Independent Set ()...
research
∙
02/25/2019
Optimal Distributed Covering Algorithms
We present a time-optimal deterministic distributed algorithm for approx...
research
∙
01/13/2019
Fast and Simple Deterministic Algorithms for Highly-Dynamic Networks
This paper provides a surprisingly simple method for obtaining fast (con...
research
∙
08/17/2018
Optimal Distributed Weighted Set Cover Approximation
We present a time-optimal deterministic distributed algorithm for approx...
research
∙
07/13/2018
Parameterized Distributed Algorithms
In this work, we initiate a thorough study of parameterized graph optimi...
research
∙
04/04/2018
A Deterministic Distributed 2-Approximation for Weighted Vertex Cover in O( n/ ^2) Rounds
We present a deterministic distributed 2-approximation algorithm for the...
research
∙
11/28/2017
Adapting Local Sequential Algorithms to the Distributed Setting
It is a well known fact that sequential algorithms which exhibit a stron...
research
∙
11/28/2017