Coresets have become an invaluable tool for solving $k$-means and kernel $k$-means clustering problems on large datasets with small numbers of clusters. On the other hand, spectral clustering works well on sparse graphs and has recently been extended to scale efficiently to large numbers of clusters. We exploit the connection between kernel $k$-means and the normalised cut problem to combine the benefits of both. Our main result is a coreset spectral clustering algorithm for graphs that clusters a coreset graph to infer a good labelling of the original graph. We prove that an $\alpha$-approximation for the normalised cut problem on the coreset graph is an $O(\alpha)$-approximation on the original. We also improve the running time of the state-of-the-art coreset algorithm for kernel $k$-means on sparse kernels, from $\tilde{O}(nk)$ to $\tilde{O}(n\cdot \min (k, d_{avg}))$, where $d_{avg}$ is the average number of non-zero entries in each row of the $n\times n$ kernel matrix. Our experiments confirm our coreset algorithm is asymptotically faster on large real-world graphs with many clusters, and show that our clustering algorithm overcomes the main challenge faced by coreset kernel $k$-means on sparse kernels which is getting stuck in local optima.

The recent advent of programmable switches makes distributed algorithms readily deployable in real-world datacenter networks. However, there are still gaps between theory and practice that prevent the smooth adaptation of CONGEST algorithms to these environments. In this paper, we focus on the memory restrictions that arise in real-world deployments. We introduce the μ-CONGEST model where on top of the bandwidth restriction, the memory of nodes is also limited to μ words, in line with real-world systems. We provide fast algorithms of two main flavors.

We introduce a novel concept termed "stochastic distance" for property testing. Diverging from the traditional definition of distance, where a distance $t$ implies that there exist $t$ edges that can be added to ensure a graph possesses a certain property (such as $k$-edge-connectivity), our new notion implies that there is a high probability that adding $t$ random edges will endow the graph with the desired property. While formulating testers based on this new distance proves challenging in a sequential environment, it is much easier in a distributed setting. Taking $k$-edge-connectivity as a case study, we design ultra-fast testing algorithms in the CONGEST model. Our introduction of stochastic distance offers a more natural fit for the distributed setting, providing a promising avenue for future research in emerging models of computation.

Abstract We present a time-optimal deterministic distributed algorithm for approximating a minimum weight vertex cover in hypergraphs of rank f. This problem is equivalent to the Minimum Weight Set Cover problem in which the frequency of every element is bounded by f. The approximation factor of our algorithm is $$(f+\varepsilon )$$ ( f + ε ) . Let $$\varDelta $$ Δ denote the maximum degree in the hypergraph. Our algorithm runs in the congest model and requires $$O(\log {\varDelta } / \log \log \varDelta )$$ O ( log Δ / log log Δ ) rounds, for constants $$\varepsilon \in (0,1]$$ ε ∈ ( 0 , 1 ] and $$f\in {\mathbb {N}}^+$$ f ∈ N + . This is the first distributed algorithm for this problem whose running time does not depend on the vertex weights nor the number of vertices. Thus adding another member to the exclusive family of provably optimal distributed algorithms. For constant values of f and $$\varepsilon $$ ε , our algorithm improves over the $$(f+\varepsilon )$$ ( f + ε ) -approximation algorithm of Kuhn et al. (SODA, 2006)whose running time is $$O(\log \varDelta + \log W)$$ O ( log Δ + log W ) , where W is the ratio between the largest and smallest vertex weights in the graph. Our algorithm also achieves an f-approximation for the problem in $$O(f\log n)$$ O ( f log n ) rounds, improving over the classical result of Khuller et al. (J Algorithms, 1994) that achieves a running time of $$O(f\log ^2 n)$$ O ( f log 2 n ) . Finally, for weighted vertex cover ( $$f=2$$ f = 2 ) our algorithm achieves a deterministic running time of $$O(\log n)$$ O ( log n ) , matching the randomized previously best result of Koufogiannakis and Young (Distrib Comput, 2011). We also show that integer covering-programs can be reduced to the Minimum Weight Set Cover problem in the distributed setting. This allows us to achieve an $$(f\lceil \log _2(M)+1 \rceil +\varepsilon )$$ ( f ⌈ log 2 ( M ) + 1 ⌉ + ε ) -approximate integral solution in $$\begin{aligned} O\left( (1+f/\log n)\cdot \left( {\frac{\log \varDelta }{ \log \log \varDelta } + ({f\cdot \log M})^{1.01}\cdot \log \varepsilon ^{-1}\cdot (\log \varDelta )^{0.01}}\right) \right) \end{aligned}$$ O ( 1 + f / log n ) · log

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 solutions in low-treewidth graphs.

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 / deleted per round. We show that the problems of k-clique membership listing (for any k≥ 3), 4-cycle listing and 5-cycle listing can be deterministically solved in O(1)-amortized round complexity, even with limited logarithmic-sized messages.

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 load balancing was extensively studied in static networks, only recently a load balancing algorithm for dynamic networks with a bounded convergence time was presented. In this paper, we further study the time complexity of load balancing in the context of dynamic networks.

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 interactions between agents, but with probability $p$ every such interaction may change into an interaction between two agents chosen uniformly at random. That is, $p$-fraction of the interactions are random, while $(1-p)$-fraction are adversarial. The aim of our model is to bridge the gap between a uniformly random scheduler (which is too idealistic) and an adversarial scheduler (which is too strict). We focus on the fundamental problem of leader election in population protocols. We show that, for a population of size $n$, the leader election problem can be solved in $O(p^{-2}n \log^3 n)$ steps with high probability, using $O((\log^2 n) \cdot (\log (n/p)))$ states per agent, for \emph{all} values of $p\leq 1$. Although our result does not match the best known running time of $O(n \log n)$ for the uniformly random scheduler ($p=1$), we are able to present a \emph{smooth transition} between a running time of $O(n \cdot \mathrm{polylog} n)$ for $p=1$ and an infinite running time for the adversarial scheduler ($p=0$), where the problem cannot be solved. The key technical contribution of our work is a novel \emph{phase clock} algorithm for our model. This is a key primitive for much-studied fundamental population protocol algorithms (leader election, majority), and we believe it is of independent interest.

This paper provides an algorithmic framework for obtaining fast distributed algorithms for a highly-dynamic setting, in which *arbitrarily many* edge changes may occur in each round. Our algorithm significantly improves upon prior work in its combination of (1) having an $O(1)$ amortized time complexity, (2) using only $O(\log{n})$-bit messages, (3) not posing any restrictions on the dynamic behavior of the environment, (4) being deterministic, (5) having strong guarantees for intermediate solutions, and (6) being applicable for a wide family of tasks. The tasks for which we deduce such an algorithm are maximal matching, $(degree+1)$-coloring, 2-approximation for minimum weight vertex cover, and maximal independent set (which is the most subtle case). For some of these tasks, node insertions can also be among the allowed topology changes, and for some of them also abrupt node deletions.

We present improved algorithms for approximating maximum-weight independent set (MaxIS) in the CONGEST model. Given an input graph, let n and Δ be the number of nodes and maximum degree, respectively, and let MIS(n, Δ) be the running time of finding a maximal independent set (MIS) in the CONGEST model. Bar-Yehuda et al. [PODC 2017] showed that there is an algorithm in the CONGEST model that finds a Δ-approximation for MaxIS in O(MIS(n, Δ) log W) rounds, where W is the maximum weight of a node in the graph, which can be as high as poly(n). Whether their algorithm is deterministic or randomized depends on the MIS algorithm that is used as a black-box. Our results:

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 n and Δ be the number of nodes and maximum degree, respectively, and let MIS(n,Δ) be the running time of finding a maximal independent set (MIS) in the CONGEST model. Bar-Yehuda et al. [PODC 2017] showed that there is an algorithm in the CONGEST model that finds a Δ-approximation for MaxIS in O(MIS(n,Δ)log W) rounds, where W is the maximum weight of a node in the graph, which can be as large as poly (n). Whether their algorithm is deterministic or randomized that succeeds with high probability depends on the MIS algorithm that is used as a black-box. Our results: 1) A deterministic O(MIS(n,Δ)/ε)-round algorithm that finds a (1+ε)Δ-approximation for MaxIS in the CONGEST model. 2) A randomized (poly(log log n)/ε)-round algorithm that finds, with high probability, a (1+ε)Δ-approximation for MaxIS in the CONGEST model. That is, by sacrificing only a tiny fraction of the approximation guarantee, we achieve an exponential speed-up in the running time over the previous best known result. 3) A randomized O(log n⋅ poly(log log n)/ε)-round algorithm that finds, with high probability, a 8(1+ε)α-approximation for MaxIS in the CONGEST model, where α is the arboricity of the graph. For graphs of arboricity α < Δ/(8(1+ε)), this result improves upon the previous best known result in both the approximation factor and the running time. One may wonder whether it is possible to approximate MaxIS with high probability in fewer than poly(log log n) rounds. Interestingly, a folklore randomized ranking algorithm by Boppana implies a single round algorithm that gives an expected Δ-approximation in the CONGEST model. However, it is unclear how to convert this algorithm to one that succeeds with high probability without sacrificing a large number of rounds. For unweighted graphs of maximum degree Δ ≤ n/log n, we show a new analysis of the randomized ranking algorithm, which we combine with the local-ratio technique, to provide a O(1/ε)-round algorithm in the CONGEST model that, with high probability, finds an independent set of size at least n/((1+ε)(Δ+1)). This result cannot be extended to very high degree graphs, as we show a lower bound of Ω(log^*n) rounds for any randomized algorithm that with probability at least 1-1/log n finds an independent set of size Ω(n/Δ). This lower bound holds even for the LOCAL model. The hard instances that we use to prove our lower bound are graphs of maximum degree Δ = Ω(n/log^*n).

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] suggested to use smoothed analysis in order to study dynamic networks. Their aim was to explain the gaps between real-world networks that function well despite being dynamic, and the strong theoretical lower bounds for arbitrary networks. To this end, they introduced a basic model of smoothing in dynamic networks, where an adversary picks a sequence of graphs, representing the topology of the network over time, and then each of these graphs is slightly perturbed in a random manner. The model suggested above is based on a per-round noise, and our aim in this work is to extend it to models of noise more suited for multiple rounds. This is motivated by long-lived networks, where the amount and location of noise may vary over time. To this end, we present several different models of noise. First, we extend the previous model to cases where the amount of noise is very small. Then, we move to more refined models, where the amount of noise can change between different rounds, e.g., as a function of the number of changes the network undergoes. We also study a model where the noise is not arbitrarily spread among the network, but focuses in each round in the areas where changes have occurred. Finally, we study the power of an adaptive adversary, who can choose its actions in accordance with the changes that have occurred so far. We use the flooding problem as a running case-study, presenting very different behaviors under the different models of noise, and analyze the flooding time in different models.

This paper addresses the cornerstone family of local problems in distributed computing, and investigates the curious gap between randomized and deterministic solutions under bandwidth restrictions. Our main contribution is in providing tools for derandomizing solutions to local problems, when the n nodes can only send \(O(\log n)\) -bit messages in each round of communication. Our framework mostly follows by the derandomization approach of Luby (J Comput Syst Sci 47(2):250–286, 1993) combined with the power of all to all communication. Our key results are as follows: first, we show that in the congested clique model, which allows all-to-all communication, there is a deterministic maximal independent set algorithm that runs in \(O(\log ^2 {\varDelta })\) rounds, where \({\varDelta }\) is the maximum degree. When \({\varDelta }=O(n^{1/3})\) , the bound improves to \(O(\log {\varDelta })\) . In addition, we deterministically construct a \((2k-1)\) -spanner with \(O(kn^{1+1/k}\log n)\) edges in \(O(k \log n)\) rounds in the congested clique model.

We present a time-optimal deterministic distributed algorithm for approximating a minimum weight vertex cover in hypergraphs of rank ƒ. This problem is equivalent to the Minimum Weight Set Cover problem in which the frequency of every element is bounded by ƒ. The approximation factor of our algorithm is (ƒ + ε). Let Δ denote the maximum degree in the hypergraph. Our algorithm runs in the CONGEST model and requires O(log Δ/log log Δ) rounds, for constants ε ∈ (0,1] and ƒ ∈ N+. This is the first distributed algorithm for this problem whose running time does not depend on the vertex weights nor the number of vertices. Thus adding another member to the exclusive family of emphprovably optimal distributed algorithms.

In this work, we initiate a thorough study of parameterized graph optimization problems in the distributed setting. In a parameterized problem, an algorithm decides whether a solution of size bounded by a \emph{parameter} $k$ exists and if so, it finds one. We study fundamental problems, including Minimum Vertex Cover (MVC), Maximum Independent Set (MaxIS), Maximum Matching (MaxM), and many others, in both the LOCAL and CONGEST distributed computation models. We present lower bounds for the round complexity of solving parameterized problems in both models, together with optimal and near-optimal upper bounds. Our results extend beyond the scope of parameterized problems. We show that any LOCAL $(1+ε)$-approximation algorithm for the above problems must take $Ω(ε^{-1})$ rounds. Joined with the algorithm of [GKM17] and the $Ω(\sqrt{\frac{\log n}{\log\log n}})$ lower bound of [KMW16], this settles the complexity of $(1+ε)$-approximating MVC, MaxM and MaxIS at $(ε^{-1}\log n)^{Θ(1)}$. We also show that our parameterized approach reduces the runtime of exact and approximate CONGEST algorithms for MVC and MaxM if the optimal solution is small, without knowing its size beforehand. Finally, we propose the first deterministic $o(n^2)$ rounds CONGEST algorithms that approximate MVC and MaxM within a factor strictly smaller than $2$.

We present a simple deterministic single-pass (2+ϵ)-approximation algorithm for the maximum weight matching problem in the semi-streaming model. This improves on the currently best known approximation ratio of (4+ϵ). Our algorithm uses O ( n log 2 n ) bits of space for constant values of ϵ. It relies on a variation of the local-ratio theorem, which may be of use for other algorithms in the semi-streaming model as well.

It is a well known fact that sequential algorithms which exhibit a strong "local" nature can be adapted to the distributed setting given a legal graph coloring. The running time of the distributed algorithm will then be at least the number of colors. Surprisingly, this well known idea was never formally stated as a unified framework. In this paper we aim to define a robust family of local sequential algorithms which can be easily adapted to the distributed setting. We then develop new tools to further enhance these algorithms, achieving state of the art results for fundamental problems. We define a simple class of greedy-like algorithms which we call \emph{orderless-local} algorithms. We show that given a legal $c$-coloring of the graph, every algorithm in this family can be converted into a distributed algorithm running in $O(c)$ communication rounds in the CONGEST model. We show that this family is indeed robust as both the method of conditional expectations and the unconstrained submodular maximization algorithm of Buchbinder \etal \cite{BuchbinderFNS15} can be expressed as orderless-local algorithms for \emph{local utility functions} --- Utility functions which have a strong local nature to them. We use the above algorithms as a base for new distributed approximation algorithms for the weighted variants of some fundamental problems: Max $k$-Cut, Max-DiCut, Max 2-SAT and correlation clustering. We develop algorithms which have the same approximation guarantees as their sequential counterparts, up to a constant additive $ε$ factor, while achieving an $O(\log^* n)$ running time for deterministic algorithms and $O(ε^{-1})$ running time for randomized ones. This improves exponentially upon the currently best known algorithms.

We present a simple distributed Δ-approximation algorithm for maximum weight independent set (MaxIS) in the CONGEST model which completes in O(MIS ⋅ log W) rounds, where Δ is the maximum degree, MIS is the number of rounds needed to compute a maximal independent set (MIS) on G, and W is the maximum weight of a node. Plugging in the best known algorithm for MIS gives a randomized solution in O(log n log W) rounds, where n is the number of nodes. We also present a deterministic O(Δ +log* n)-round algorithm based on coloring.

We present a simple deterministic single-pass (2 + ∊)-approximation algorithm for the maximum weight matching problem in the semi-streaming model. This improves upon the currently best known approximation ratio of (3.5 + ∊). Our algorithm uses O(n log2 n) space for constant values of e. It relies on a variation of the local-ratio theorem, which may be of independent interest in the semi-streaming model.

We present a simple deterministic distributed (2 + ϵ)-approximation algorithm for minimum-weight vertex cover, which completes in O (log Δ/ϵlog log Δ) rounds, where Δ is the maximum degree in the graph, for any ϵ > 0 that is at most O (1). For a constant ϵ, this implies a constant approximation in O (log Δ/log log Δ) rounds, which contradicts the lower bound of [KMW10].

We present a simple deterministic distributed (2+ε) approximation algorithm for minimum weight vertex cover, which completes in O(logδ/εlog logδ) rounds, where δ is the maximum degree in the graph, for any ε > 0 which is at most O(1). For a constant ε, this implies a constant approximation in Ologδ/log log δ) rounds, which contradicts the lower bound of [KMW10].