4 citations · 4 across the 3 of their papers we have counts for
13 papers · 1 filter
Fully Polynomial-Time Distributed Computation in Low-Treewidth Graphs
Taisuke Izumi, Naoki Kitamura, Takamasa Naruse +1
We consider global problems, i.e. problems that take at least diameter time, even when the bandwidth is not restricted. We show that all problems considered admit efficient solutio…
On the Complexity of Load Balancing in Dynamic Networks
Seth Gilbert, Uri Meir, Ami Paz +1
In the load balancing problem, each node in a network is assigned a load, and the goal is to equally distribute the loads among the nodes, by preforming local load exchanges. While…
Smoothed Analysis of Population Protocols
Gregory Schwartzman, Yuichi Sudo
In this work, we initiate the study of \emph{smoothed analysis} of population protocols. We consider a population protocol model where an adaptive adversary dictates the interactio…
Models of Smoothing in Dynamic Networks
Uri Meir, Ami Paz, Gregory Schwartzman
Smoothed analysis is a framework suggested for mediating gaps between worst-case and average-case complexities. In a recent work, Dinitz et al.~[Distributed Computing, 2018] sugges…
Finding Subgraphs in Highly Dynamic Networks
Keren Censor-Hillel, Victor I. Kolobov, Gregory Schwartzman
In this paper we consider the fundamental problem of finding subgraphs in highly dynamic distributed networks - networks which allow an arbitrary number of links to be inserted / d…
Improved Distributed Approximations for Maximum Independent Set
Ken-ichi Kawarabayashi, Seri Khoury, Aaron Schild +1
We present improved results for approximating maximum-weight independent set ($\MaxIS$) in the CONGEST and LOCAL models of distributed computing. Given an input graph, let and…