Search

We present the first mini-batch kernel $k$-means algorithm, offering an order of magnitude improvement in running time compared to the full batch algorithm. A single iteration of our algorithm takes $\widetilde{O}(kb^2)$ time, significantly faster than the $O(n^2)$ time required by the full batch kernel $k$-means, where $n$ is the dataset size and $b$ is the batch size. Extensive experiments demonstrate that our algorithm consistently achieves a 10-100x speedup with minimal loss in quality, addressing the slow runtime that has limited kernel $k$-means adoption in practice. We further complement these results with a theoretical analysis under an early stopping condition, proving that with a batch size of $\widetilde{\Omega}(\max \{\gamma^{4}, \gamma^{2}\} \cdot \epsilon^{-2})$, the algorithm terminates in $O(\gamma^2/\epsilon)$ iterations with high probability, where $\gamma$ bounds the norm of points in feature space and $\epsilon$ is a termination threshold. Our analysis holds for any reasonable center initialization, and when using $k$-means++ initialization, the algorithm achieves an approximation ratio of $O(\log k)$ in expectation. For normalized kernels, such as Gaussian or Laplacian it holds that $\gamma=1$. Taking $\epsilon = O(1)$ and $b=\Theta(\log n)$, the algorithm terminates in $O(1)$ iterations, with each iteration running in $\widetilde{O}(k)$ time., Comment: arXiv admin note: text overlap with arXiv:2304.00419

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., Comment: To be published in RANDOM 2024

We report that ChatGPT 4 and 4o are susceptible to a prompt injection attack that allows an attacker to exfiltrate users' personal data. It is applicable without the use of any 3rd party tools and all users are currently affected. This vulnerability is exacerbated by the recent introduction of ChatGPT's memory feature, which allows an attacker to command ChatGPT to monitor the user for the desired personal data.

We present the first mini-batch algorithm for maximizing a non-negative monotone decomposable submodular function, $F=\sum_{i=1}^N f^i$, under a set of constraints. We consider two sampling approaches: uniform and weighted. We first show that mini-batch with weighted sampling improves over the state of the art sparsifier based approach both in theory and in practice. Surprisingly, our experimental results show that uniform sampling is superior to weighted sampling. However, it is impossible to explain this using worst-case analysis. Our main contribution is using smoothed analysis to provide a theoretical foundation for our experimental results. We show that, under very mild assumptions, uniform sampling is superior for both the mini-batch and the sparsifier approaches. We empirically verify that these assumptions hold for our datasets. Uniform sampling is simple to implement and has complexity independent of $N$, making it the perfect candidate to tackle massive real-world datasets.

We bound the smoothed running time of the FLIP algorithm for local Max-Cut as a function of $\alpha$, the arboricity of the input graph. We show that, with high probability and in expectation, the following holds (where $n$ is the number of nodes and $\phi$ is the smoothing parameter): 1) When $\alpha = O(\log^{1-\delta} n)$ FLIP terminates in $\phi poly(n)$ iterations, where $\delta \in (0,1]$ is an arbitrarily small constant. Previous to our results the only graph families for which FLIP was known to achieve a smoothed polynomial running time were complete graphs and graphs with logarithmic maximum degree. 2) For arbitrary values of $\alpha$ we get a running time of $\phi n^{O(\frac{\alpha}{\log n} + \log \alpha)}$. This improves over the best known running time for general graphs of $\phi n^{O(\sqrt{ \log n })}$ for $\alpha = o(\log^{1.5} n)$. Specifically, when $\alpha = O(\log n)$ we get a significantly faster running time of $\phi n^{O(\log \log n)}$.

We answer the question: "Does local progress (on batches) imply global progress (on the entire dataset) for mini-batch $k$-means?". Specifically, we consider mini-batch $k$-means which terminates only when the improvement in the quality of the clustering on the sampled batch is below some threshold. Although at first glance it appears that this algorithm might execute forever, we answer the above question in the affirmative and show that if the batch is of size $\tilde{\Omega}((d/\epsilon)^2)$, it must terminate within $O(d/\epsilon)$ iterations with high probability, where $d$ is the dimension of the input, and $\epsilon$ is a threshold parameter for termination. This is true regardless of how the centers are initialized. When the algorithm is initialized with the $k$-means++ initialization scheme, it achieves an approximation ratio of $O(\log k)$ (the same as the full-batch version). Finally, we show the applicability of our results to the mini-batch $k$-means algorithm implemented in the scikit-learn (sklearn) python library., Comment: ICLR 2023

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. By ``efficient'' we mean that the running time has polynomial dependence on the treewidth, a linear dependence on the diameter (which is unavoidable), and only a polylogarithmic dependence on $n$, the number of nodes in the graph. We present the algorithms solving the following problems in the CONGEST model which all attain $\tilde{O(\tau^{O(1)}D)}$-round complexity (where $\tau$ and $D$ denote the treewidth and diameter of the graph, respectively): (1) Exact single-source shortest paths (actually, the more general problem of computing a distance labeling scheme) for weighted and directed graphs, (2) exact bipartite unweighted maximum matching, and (3) the weighted girth for both directed and undirected graphs. We derive all of our results using a single unified framework, which consists of two novel technical ingredients, The first is a fully polynomial-time distributed tree decomposition algorithm, which outputs a decomposition of width $O(\tau^2\log n)$ in $\tilde{O}(\tau^{O(1)}D)$ rounds (where $n$ is the number of nodes in the graph). The second ingredient, and the technical highlight of this paper, is the novel concept of a \emph{stateful walk constraint}, which naturally defines a set of feasible walks in the input graph based on their local properties (e.g., augmenting paths). Given a stateful walk constraint, the constrained version of the shortest paths problem (or distance labeling) requires the algorithm to output the shortest \emph{constrained} walk (or its distance) for a given source and sink vertices. We show that this problem can be efficiently solved in the CONGEST model by reducing it to an \emph{unconstrained} version of the problem.

Distributed protocols are widely used to support network functions such as clock synchronization and multicast. As the network gets larger and faster, it is increasingly challenging for these protocols to react quickly to network events. The theory community has made significant progress in developing distributed message passing algorithms with improved convergence times. With the emerging programmability at switches, it now becomes feasible to adopt and adapt these theoretical advances for networking functions. In this paper, we propose FRANCIS, a new framework for running message passing algorithms on programmable switches to enable fast reactions to network events in large networks. We introduce an execution engine with computing and communication primitives for supporting message passing algorithms in P4 switches. We exemplify the framework's usefulness by improving the resiliency and reaction times of clock synchronization and source-routed multicast. In particular, our approach allows lower clock drift than Sundial and PTP, quickly recovers from multiple failures, and reduces the time uncertainty bound by up to 5x. Compared with state-of-the-art multicast solutions, our approach uses packet headers up to 33\% smaller and has an order of magnitude faster reaction time.

We prove that stochastic gradient descent (SGD) finds a solution that achieves $(1-\epsilon)$ classification accuracy on the entire dataset. We do so under two main assumptions: (1. Local progress) The model accuracy improves on average over batches. (2. Models compute simple functions) The function computed by the model is simple (has low Kolmogorov complexity). It is sufficient that these assumptions hold only for a tiny fraction of the epochs. Intuitively, the above means that intermittent local progress of SGD implies global progress. Assumption 2 trivially holds for underparameterized models, hence, our work gives the first convergence guarantee for general, underparameterized models. Furthermore, this is the first result which is completely model agnostic - we do not require the model to have any specific architecture or activation function, it may not even be a neural network. Our analysis makes use of the entropy compression method, which was first introduced by Moser and Tardos in the context of the Lov\'asz local lemma.

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. First, we show that randomness is not necessary, and present a deterministic algorithm which slightly improves the running time of the previous algorithm, at the price of not being matching-based. Then, we consider integral loads, i.e., loads that cannot be split indefinitely, and prove that no matching-based algorithm can have a bounded convergence time for this case. To circumvent both this impossibility result, and a known one for the non-integral case, we apply the method of smoothed analysis, where random perturbations are made over the worst-case choices of network topologies. We show both impossibility results do not hold under this kind of analysis, suggesting that load-balancing in real world systems might be faster than the lower bounds suggest., Comment: To be presented in SPAA 2021

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.

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.

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\geq 3$), 4-cycle listing and 5-cycle listing can be deterministically solved in $O(1)$-amortized round complexity, even with limited logarithmic-sized messages. To achieve $k$-clique membership listing we introduce a very useful combinatorial structure which we name the robust $2$-hop neighborhood. This is a subset of the 2-hop neighborhood of a node, and we prove that it can be maintained in highly dynamic networks in $O(1)$-amortized rounds. We also show that maintaining the actual 2-hop neighborhood of a node requires near linear amortized time, showing the necessity of our definition. For $4$-cycle and $5$-cycle listing, we need edges within hop distance 3, for which we similarly define the robust $3$-hop neighborhood and prove it can be maintained in highly dynamic networks in $O(1)$-amortized rounds. We complement the above with several impossibility results. We show that membership listing of any other graph on $k\geq 3$ nodes except $k$-clique requires an almost linear number of amortized communication rounds. We also show that $k$-cycle listing for $k\geq 6$ requires $\Omega(\sqrt{n} / \log n)$ amortized rounds. This, combined with our upper bounds, paints a detailed picture of the complexity landscape for ultra fast graph finding algorithms in this highly dynamic environment.

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 $\Delta$ be the number of nodes and maximum degree, respectively, and let $\MIS(n,\Delta)$ be the the running time of finding a \emph{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 $\Delta$-approximation for $\MaxIS$ in $O(\MIS(n,\Delta)\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 main result in this work is a randomized $(\poly(\log\log n)/\epsilon)$-round algorithm that finds, with high probability, a $(1+\epsilon)\Delta$-approximation for $\MaxIS$ in the CONGEST model. That is, by sacrificing only a tiny fraction of the approximation guarantee, we achieve an \emph{exponential} speed-up in the running time over the previous best known result. Due to a lower bound of $\Omega(\sqrt{\log n/\log \log n})$ that was given by Kuhn, Moscibroda and Wattenhofer [JACM, 2016] on the number of rounds for any (possibly randomized) algorithm that finds a maximal independent set (even in the LOCAL model) this result implies that finding a $(1+\epsilon)\Delta$-approximation for $\MaxIS$ is exponentially easier than $\MIS$., Comment: This version contains improved results compared to the previous one

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+\epsilon)$. Our algorithm runs in the CONGEST model and requires $O(\log\Delta/ \log\log\Delta)$ rounds, for constants $\epsilon\in(0,1]$ and $f\in 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. For constant values of $f$ and $\epsilon$, our algorithm improves over the $(f+\epsilon)$-approximation algorithm of KMW06 whose running time is $O(\log \Delta + \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)$ rounds, improving over the classical result of KVY94 that achieves a running time of $O(f\log^2 n)$. Finally, for weighted vertex cover ($f=2$) our algorithm achieves a \emph{deterministic} running time of $O(\log n)$, matching the \emph{randomized} previously best result of KY11. 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+\epsilon)$-approximate integral solution in $O(\frac{\log\Delta}{\log\log\Delta}+(f\cdot\log M)^{1.01}\log\epsilon^{-1}(\log\Delta)^{0.01})$ rounds, where $f$ bounds the number of variables in a constraint, $\Delta$ bounds the number of constraints a variable appears in, and $M=\max \{1, 1/a_{\min}\}$, where $a_{min}$ is the smallest normalized constraint coefficient. This improves over the results of KMW06 for the integral case, which runs in $O(\epsilon^{-4}\cdot f^4\cdot \log f\cdot\log(M\cdot\Delta))$ rounds., Comment: This paper extends and improves arXiv:1808.05809 which we keep separate as it is considerably simpler

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 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+\epsilon)$. Let $\Delta$ denote the maximum degree in the hypergraph. Our algorithm runs in the CONGEST model and requires $O(\log{\Delta} / \log \log \Delta)$ rounds, for constants $\epsilon \in (0,1]$ and $f\in\mathbb N^+$. This is the first distributed algorithm for this problem whose running time does not depend on the vertex weights or the number of vertices. Thus adding another member to the exclusive family of \emph{provably optimal} distributed algorithms. For constant values of $f$ and $\epsilon$, our algorithm improves over the $(f+\epsilon)$-approximation algorithm of \cite{KuhnMW06} whose running time is $O(\log \Delta + \log W)$, where $W$ is the ratio between the largest and smallest vertex weights in the graph.

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+\epsilon)$-approximation algorithm for the above problems must take $\Omega(\epsilon^{-1})$ rounds. Joined with the algorithm of [GKM17] and the $\Omega(\sqrt{\frac{\log n}{\log\log n}})$ lower bound of [KMW16], this settles the complexity of $(1+\epsilon)$-approximating MVC, MaxM and MaxIS at $(\epsilon^{-1}\log n)^{\Theta(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 deterministic distributed $2$-approximation algorithm for the Minimum Weight Vertex Cover problem in the CONGEST model whose round complexity is $O(\log n \log \Delta / \log^2 \log \Delta)$. This improves over the currently best known deterministic 2-approximation implied by [KVY94]. Our solution generalizes the $(2+\epsilon)$-approximation algorithm of [BCS17], improving the dependency on $\epsilon^{-1}$ from linear to logarithmic. In addition, for every $\epsilon=(\log \Delta)^{-c}$, where $c\geq 1$ is a constant, our algorithm computes a $(2+\epsilon)$-approximation in $O(\log \Delta / \log \log \Delta)$~rounds (which is asymptotically optimal)., Comment: To appear in SIROCCO 2018

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 $\epsilon$ factor, while achieving an $O(\log^* n)$ running time for deterministic algorithms and $O(\epsilon^{-1})$ running time for randomized ones. This improves exponentially upon the currently best known algorithms.

We present a simple distributed $\Delta$-approximation algorithm for maximum weight independent set (MaxIS) in the $\mathsf{CONGEST}$ model which completes in $O(\texttt{MIS}(G)\cdot \log W)$ rounds, where $\Delta$ is the maximum degree, $\texttt{MIS}(G)$ is the number of rounds needed to compute a maximal independent set (MIS) on $G$, and $W$ is the maximum weight of a node. %Whether our algorithm is randomized or deterministic depends on the \texttt{MIS} algorithm used as a black-box. 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(\Delta +\log^* n)$-round algorithm based on coloring. We then show how to use our MaxIS approximation algorithms to compute a $2$-approximation for maximum weight matching without incurring any additional round penalty in the $\mathsf{CONGEST}$ model. We use a known reduction for simulating algorithms on the line graph while incurring congestion, but we show our algorithm is part of a broad family of \emph{local aggregation algorithms} for which we describe a mechanism that allows the simulation to run in the $\mathsf{CONGEST}$ model without an additional overhead. Next, we show that for maximum weight matching, relaxing the approximation factor to ($2+\varepsilon$) allows us to devise a distributed algorithm requiring $O(\frac{\log \Delta}{\log\log\Delta})$ rounds for any constant $\varepsilon>0$. For the unweighted case, we can even obtain a $(1+\varepsilon)$-approximation in this number of rounds. These algorithms are the first to achieve the provably optimal round complexity with respect to dependency on $\Delta$.

We present a simple deterministic single-pass $(2+\epsilon)$-approximation algorithm for the maximum weight matching problem in the semi-streaming model. This improves upon the currently best known approximation ratio of $(4+\epsilon)$. Our algorithm uses $O(n\log^2 n)$ bits of space for constant values of $\epsilon$. 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.

This paper addresses the cornerstone family of \emph{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. We combine bounded independence, which we show to be sufficient for some algorithms, with the method of conditional expectations and with additional machinery, to obtain the following results. Our techniques give a deterministic maximal independent set (MIS) algorithm in the CONGEST model, where the communication graph is identical to the input graph, in $O(D\log^2 n)$ rounds, where $D$ is the diameter of the graph. The best known running time in terms of $n$ alone is $2^{O(\sqrt{\log n})}$, which is super-polylogarithmic, and requires large messages. For the CONGEST model, the only known previous solution is a coloring-based $O(\Delta + \log^* n)$-round algorithm, where $\Delta$ is the maximal degree in the graph. On the way to obtaining the above, we show that in the \emph{Congested Clique} model, which allows all-to-all communication, there is a deterministic MIS algorithm that runs in $O(\log \Delta \log n)$ rounds.%, where $\Delta$ is the maximum degree. When $\Delta=O(n^{1/3})$, the bound improves to $O(\log \Delta)$ and holds also for $(\Delta+1)$-coloring. In addition, we deterministically construct a $(2k-1)$-spanner with $O(kn^{1+1/k}\log n)$ edges in $O(k \log n)$ rounds. For comparison, in the more stringent CONGEST model, the best deterministic algorithm for constructing a $(2k-1)$-spanner with $O(kn^{1+1/k})$ edges runs in $O(n^{1-1/k})$ rounds.

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

We initiate a thorough study of \emph{distributed property testing} -- producing algorithms for the approximation problems of property testing in the CONGEST model. In particular, for the so-called \emph{dense} testing model we emulate sequential tests for nearly all graph properties having $1$-sided tests, while in the \emph{sparse} and \emph{general} models we obtain faster tests for triangle-freeness and bipartiteness respectively. In most cases, aided by parallelism, the distributed algorithms have a much shorter running time as compared to their counterparts from the sequential querying model of traditional property testing. The simplest property testing algorithms allow a relatively smooth transitioning to the distributed model. For the more complex tasks we develop new machinery that is of independent interest. This includes a method for distributed maintenance of multiple random walks.