5 papers
Smoothed Analysis of Dynamic Graph Algorithms
Uri Meir, Ami Paz
Recent years have seen significant progress in the study of dynamic graph algorithms, and most notably, the introduction of strong lower bound techniques for them (e.g., Henzinger,…
Stochastic Distance in Property Testing
Uri Meir, Gregory Schwartzman, Yuichi Yoshida
We introduce a novel concept termed "stochastic distance" for property testing. Diverging from the traditional definition of distance, where a distance implies that there exist…
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…
Comparison Graphs: a Unified Method for Uniformity Testing
Uri Meir
Distribution testing can be described as follows: samples are being drawn from some unknown distribution over a known domain . After the sampling process, a decision m…
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…