Abstract In this work we present the first constant-round algorithms for computing spanners and approximate All-Pairs Shortest Paths (APSP) in the distributed Congested Clique model. Specifically, we show the following results for undirected n -node graphs. For every integer $$k \ge 1$$ , O (1)-round algorithms for constructing O ( k )-spanners with $$O(n^{1+1/k})$$ edges in unweighted graphs, and O ( k )-spanners with $$O(n^{1+1/k} \log {n})$$ edges in weighted graphs. An O (1)-round algorithm for $$O(\log {n})$$ -approximation for APSP in unweighted graphs. An O (1)-round algorithm for $$O(\log ^2{n})$$ -approximation for APSP in weighted graphs. All our algorithms are randomized and succeed with high probability. Prior to our work, the fastest algorithms for computing O ( k )-spanners in this model require $${{\,\textrm{poly}\,}}(\log {k})$$ rounds [Parter, Yogev, DISC ’18] [Biswas, Dory, Ghaffari, Mitrovic, Nazari, SPAA ’21], and the fastest algorithms for approximate shortest paths require $${{\,\textrm{poly}\,}}(\log {\log {n}})$$ rounds [Dory, Parter, PODC ’20]. Our results extend to the closely related massively parallel computation (MPC) model with near-linear memory per machine, leading to the first O (1)-round algorithms for spanners and approximate shortest paths in this model as well.

Transformers have revolutionized the field of machine learning. In particular, they can be used to solve complex algorithmic problems, including graph-based tasks. In such algorithmic tasks a key question is what is the minimal size of a transformer that can implement the task. Recent work has begun to explore this problem for graph-based tasks, showing that for sub-linear embedding dimension (i.e., model width) logarithmic depth suffices. However, an open question, which we address here, is what happens if width is allowed to grow linearly, while depth is kept fixed. Here we analyze this setting, and provide the surprising result that with linear width, constant depth suffices for solving a host of graph-based problems. This suggests that a moderate increase in width can allow much shallower models, which are advantageous in terms of inference and train time. For other problems, we show that quadratic width is required. Our results demonstrate the complex and intriguing landscape of transformer implementations of graph-based algorithms. We empirically investigate these trade-offs between the relative powers of depth and width and find tasks where wider models have the same accuracy as deep models, while having much faster train and inference time due to parallelizable hardware.

Resilient computation in all-to-all-communication models has attracted tremendous attention over the years. Most of these works assume the classical faulty model which restricts the total number of corrupted edges (or vertices) by some integer fault parameter f. A recent work by [Bodwin, Haeupler and Parter, SODA 2024] introduced a stronger notion of fault-tolerance, in the context of graph sparsification, which restricts the degree of the failing edge set F, rather than its cardinality. For a subset of faulty edges F, the faulty-degree deg(F) is the largest number of faults in F incident to any given node.

Pointer-chasing is a central problem in two-party communication complexity: given input size n and a parameter k, the two players Alice and Bob are given functions $$N_A, N_B: [n] \rightarrow [n]$$ , respectively, and their goal is to compute the value of $$p_k$$ , where $$p_0 = 1$$ , $$p_1 = N_A(p_0)$$ , $$p_2 = N_B(p_1) = N_B(N_A(p_0))$$ , $$p_3 = N_A(p_2) = N_A(N_B(N_A(p_0)))$$ and so on, applying $$N_A$$ in even steps and $$N_B$$ in odd steps, for a total of k steps. In some versions of the problem, the final output is not $$p_k$$ itself, but rather some fixed function $$f(p_k)$$ of $$p_k$$ . It is trivial to solve the problem using k communication rounds, with Alice speaking first, by simply “chasing the function” for k steps. Many works have studied the communication complexity of pointer chasing, although the focus has always been on protocols with $$k-1$$ communication rounds, or with k rounds where Bob (the “wrong player”) speaks first. Many works have studied this setting giving sometimes tight or near-tight results. In this paper we study the communication complexity of the pointer chasing problem when the interaction between the two players is unlimited, i.e., without any restriction on the number of rounds. Perhaps surprisingly, this question was not studied before, to the best of our knowledge. Our main result is that the trivial k-round protocol is nearly tight (even) when the number of rounds is not restricted: we give a lower bound of $$\varOmega (k \log (n/k))$$ on the randomized communication complexity of the pointer chasing problem with unlimited interaction, and a somewhat stronger lower bound of $$\varOmega (k \log \log {k})$$ for protocols with zero error. When combined with prior work, our results also give a nearly-tight bound on the communication complexity of protocols using at most $$k-1$$ rounds, across all regimes of k; for $$k > \sqrt{n}$$ there was previously a significant gap between the upper and lower bound.

Abstract Massively-parallel graph algorithms have received extensive attention over the past decade, with research focusing on three memory regimes: the superlinear regime, the near-linear regime, and the sublinear regime. The sublinear regime is the most desirable in practice, but conditional hardness results point towards its limitations. In this work we study a heterogeneous model, where the memory of the machines varies in size. We focus mostly on the heterogeneous setting created by adding a single near-linear machine to the sublinear MPC regime, and show that even a single large machine suffices to circumvent most of the conditional hardness results for the sublinear regime: for graphs with n vertices and m edges, we give (a) an MST algorithm that runs in $$O(\log \log (m/n))$$ O ( log log ( m / n ) ) rounds; (b) an algorithm that constructs an O(k)-spanner of size $$O(n^{1+1/k})$$ O ( n 1 + 1 / k ) in O(1) rounds; and (c) a maximal-matching algorithm that runs in $$O(\sqrt{\log (m/n)}\log \log (m/n))$$ O ( log ( m / n ) log log ( m / n ) ) rounds. We also observe that the best known near-linear MPC algorithms for several other graph problems which are conjectured to be hard in the sublinear regime (minimum cut, maximal independent set, and vertex coloring) can easily be transformed to work in the heterogeneous MPC model with a single near-linear machine, while retaining their original round complexity in the near-linear regime. If the large machine is allowed to have superlinear memory, all of the problems above can be solved in O(1) rounds.

Contrastive learning is a highly successful technique for learning representations of data from labeled tuples, specifying the distance relations within the tuple. We study the sample complexity of contrastive learning, i.e. the minimum number of labeled tuples sufficient for getting high generalization accuracy. We give tight bounds on the sample complexity in a variety of settings, focusing on arbitrary distance functions, $\ell_p$-distances, and tree metrics. Our main result is an (almost) optimal bound on the sample complexity of learning $\ell_p$-distances for integer $p$. For any $p \ge 1$, we show that $\tilde \Theta(nd)$ labeled tuples are necessary and sufficient for learning $d$-dimensional representations of $n$-point datasets. Our results hold for an arbitrary distribution of the input samples and are based on giving the corresponding bounds on the Vapnik-Chervonenkis/Natarajan dimension of the associated problems. We further show that the theoretical bounds on sample complexity obtained via VC/Natarajan dimension can have strong predictive power for experimental results, in contrast with the folklore belief about a substantial gap between the statistical learning theory and the practice of deep learning.

We study the embedding dimension of distance comparison data in two settings: contrastive learning and $k$-nearest neighbors ($k$-NN). In both cases, the goal is to find the smallest dimension $d$ of an $\ell_p$-space in which a given dataset can be represented. We show that the arboricity of the associated graphs plays a key role in designing embeddings. Using this approach, for the most frequently used $\ell_2$-distance, we get matching upper and lower bounds in both settings. In contrastive learning, we are given $m$ labeled samples of the form $(x_i, y_i^+, z_i^-)$ representing the fact that the positive example $y_i$ is closer to the anchor $x_i$ than the negative example $z_i$. We show that for representing such dataset in: - $\ell_2$: $d = \Theta(\sqrt{m})$ is necessary and sufficient. - $\ell_p$ for $p \ge 1$: $d = O(m)$ is sufficient and $d = \tilde \Omega(\sqrt{m})$ is necessary. - $\ell_\infty$: $d = O(m^{2/3})$ is sufficient and $d = \tilde \Omega(\sqrt{m})$ is necessary. We also give results for the more general scenario when $t$ negatives are allowed. In $k$-NN, for each of the $n$ data points we are given an ordered set of the closest $k$ points. We show that for preserving the ordering of the $k$-NN for every point in: - $\ell_2$: $d = \Theta(k)$ is necessary and sufficient. - $\ell_p$ for $p \ge 1$: $d = \tilde O(k^2)$ is sufficient and $d=\tilde \Omega(k)$ is necessary. - $\ell_\infty$ : $d = \tilde \Omega(k)$ is necessary. Furthermore, if the goal is to not just preserve the ordering of the $k$-NN but also keep them as the nearest neighbors then $d = \tilde O (\mathrm{poly}(k))$ suffices in $\ell_p$ for $p \ge 1$.

We study the problem of learning a hierarchical tree representation of data from labeled samples, taken from an arbitrary (and possibly adversarial) distribution. Consider a collection of data tuples labeled according to their hierarchical structure. The smallest number of such tuples required in order to be able to accurately label subsequent tuples is of interest for data collection in machine learning. We present optimal sample complexity bounds for this problem in several learning settings, including (agnostic) PAC learning and online learning. Our results are based on tight bounds of the Natarajan and Littlestone dimensions of the associated problem. The corresponding tree classifiers can be constructed efficiently in near-linear time.

In their seminal PODC 1991 paper, Ostrovsky and Yung introduced the study of distributed computation in the presence of mobile adversaries which can dynamically appear throughout the network, analogous to a spread of a virus. Over the years, this setting has been studied mostly under the assumption that the communication graph is fully-connected. Resilient CONGEST algorithms for general graphs, on the other hand, are currently known only for the classical static setting, i.e., where the set of corrupted edges (or nodes) is fixed throughout the entire computation.

Massively-parallel graph algorithms have received extensive attention over the past decade, with research focusing on three memory regimes: the superlinear regime, the near-linear regime, and the sublinear regime. The sublinear regime is the most desirable in practice, but conditional hardness results point towards its limitations. In this work we study a heterogeneous model, where the memory of the machines varies in size. We focus mostly on the heterogeneous setting created by adding a single near-linear machine to the sublinear MPC regime, and show that even a single large machine suffices to circumvent most of the conditional hardness results for the sublinear regime: for graphs with n vertices and m edges, we give (a) an MST algorithm that runs in O(łogłog(m/n)) rounds; (b) an algorithm that constructs an O(k)-spanner of size O(n^1+1/k ) in O(1) rounds; and (c) a maximal-matching algorithm that runs in O(√łog(m/n) łogłog(m/n)) rounds. We also observe that the best known near-linear MPC algorithms for several other graph problems which are conjectured to be hard in the sublinear regime (minimum cut, maximal independent set, and vertex coloring) can easily be transformed to work in the heterogeneous MPC model with a single near-linear machine, while retaining their original round complexity in the near-linear regime. If the large machine is allowed to have superlinear memory, all of the problems above can be solved in O(1) rounds.

In this work we present the first constant-round algorithms for computing spanners and approximate All-Pairs Shortest Paths (APSP) in the distributed CONGESTED CLIQUE model. Specifically, we show the following results for undirected n-node graphs. ulFor every integer k ≥ 1, O(1)-round algorithms for constructing O(k)-spanners with O(n1+1/k) edges in unweighted graphs, and O(k)-spanners with O(n1+1/k log n) edges in weighted graphs. An O(1)-round algorithm for O(log n)-approximation for APSP in unweighted graphs. An O(1)-round algorithm for O(log2n)-approximation for APSP in weighted graphs. All our algorithms are randomized and succeed with high probability. Prior to our work, the fastest algorithms for computing O(k)-spanners in this model require poly(log k) rounds [Parter, Yogev, DISC '18] [Biswas et al., SPAA '21], and the fastest algorithms for approximate shortest paths require poly(log log n) rounds [Dory, Parter, PODC '20]. Our results extend to the closely related massively parallel computation (MPC) model with near-linear memory per machine, leading to the first O(1)-round algorithms for spanners and approximate shortest paths in this model as well.

In this paper we give fast distributed graph algorithms for detecting and listing small subgraphs, and for computing or approximating the girth. Our algorithms improve upon the state of the art by polynomial factors, and for girth, we obtain a constant-time algorithm for additive +1 approximation in Congested Clique, and the first parametrized algorithm for exact computation in Congest. In the Congested Clique model, we first develop a technique for learning small neighborhoods, and apply it to obtain an O(1)-round algorithm that computes the girth with only an additive +1 error. Next, we introduce a new technique (the partition tree technique) allowing for efficiently listing all copies of any subgraph, which is deterministic and improves upon the state-of the-art for non-dense graphs. We give two concrete applications of the partition tree technique: First we show that for constant k, it is possible to solve C_{2k}-detection in O(1) rounds in the Congested Clique, improving on prior work, which used fast matrix multiplication and thus had polynomial round complexity. Second, we show that in triangle-free graphs, the girth can be exactly computed in time polynomially faster than the best known bounds for general graphs. We remark that no analogous result is currently known for sequential algorithms. In the Congest model, we describe a new approach for finding cycles, and instantiate it in two ways: first, we show a fast parametrized algorithm for girth with round complexity Õ(min{g⋅ n^{1-1/Θ(g)},n}) for any girth g; and second, we show how to find small even-length cycles C_{2k} for k = 3,4,5 in O(n^{1-1/k}) rounds. This is a polynomial improvement upon the previous running times; for example, our C₆-detection algorithm runs in O(n^{2/3}) rounds, compared to O(n^{3/4}) in prior work. Finally, using our improved C₆-freeness algorithm, and the barrier on proving lower bounds on triangle-freeness of Eden et al., we show that improving the current ̃Ω(√n) lower bound for C₆-freeness of Korhonen et al. by any polynomial factor would imply strong circuit complexity lower bounds.

In this paper we give sublinear-time distributed algorithms in the CONGEST model for subgraph detection for two classes of graphs: cliques and even-length cycles. We show for the first time that all copies of 4-cliques and 5-cliques in the network graph can be listed in sublinear time, O(n^{5/6+o(1)}) rounds and O(n^{21/22+o(1)}) rounds, respectively. Prior to our work, it was not known whether it was possible to even check if the network contains a 4-clique or a 5-clique in sublinear time. For even-length cycles, C_{2k}, we give an improved sublinear-time algorithm, which exploits a new connection to extremal combinatorics. For example, for 6-cycles we improve the running time from O~(n^{5/6}) to O~(n^{3/4}) rounds. We also show two obstacles on proving lower bounds for C_{2k}-freeness: First, we use the new connection to extremal combinatorics to show that the current lower bound of Omega~(sqrt{n}) rounds for 6-cycle freeness cannot be improved using partition-based reductions from 2-party communication complexity, the technique by which all known lower bounds on subgraph detection have been proven to date. Second, we show that there is some fixed constant delta in (0,1/2) such that for any k, a Omega(n^{1/2+delta}) lower bound on C_{2k}-freeness implies new lower bounds in circuit complexity. For general subgraphs, it was shown in [Orr Fischer et al., 2018] that for any fixed k, there exists a subgraph H of size k such that H-freeness requires Omega~(n^{2-Theta(1/k)}) rounds. It was left as an open problem whether this is tight, or whether some constant-sized subgraph requires truly quadratic time to detect. We show that in fact, for any subgraph H of constant size k, the H-freeness problem can be solved in O(n^{2 - Theta(1/k)}) rounds, nearly matching the lower bound of [Orr Fischer et al., 2018].

In the directed minimum spanning tree problem (DMST, also called minimum weight arborescence), the network is given a root node r, and needs to construct a minimum-weight directed spanning tree, rooted at r and oriented outwards. In this paper we present the first sub-quadratic DMST algorithms in the distributed CONGEST network model, where the messages exchanged between the network nodes are bounded in size. We consider three versions: a model where the communication links are bidirectional but can have different weights in the two directions; a model where communication is unidirectional; and the Congested Clique model, where all nodes can communicate directly with each other. Our algorithm is based on a variant of Lovász' DMST algorithm for the PRAM model, and uses a distributed single-source shortest-path (SSSP) algorithm for directed graphs as a black box. In the bidirectional CONGEST model, our algorithm has roughly the same running time as the SSSP algorithm; using the state-of-the-art SSSP algorithm, we obtain a running time of O~(min(sqrt{nD},sqrt{n}D^{1/4} + n^{3/5} +D)) rounds for the bidirectional communication case. For the unidirectional communication model we give an O~(n) algorithm, and show that it is nearly optimal. And finally, for the Congested Clique, our algorithm again matches the best known SSSP algorithm: it runs in O~(n^{1/3}) rounds. On the negative side, we adapt an observation of Chechik in the sequential setting to show that in all three models, the DMST problem is at least as hard as the (s,t)-shortest path problem. Thus, in terms of round complexity, distributed DMST lies between single-source shortest path and (s,t)-shortest path.

In the distributed subgraph detection problem, we are given a fixed subgraph H , and the network must decide whether the network graph contains a copy of H or not. Subgraph detection can be solved in a constant number of rounds if message size is unbounded, but in the CONGEST model, where each message has bounded size, it can have high round complexity. Distributed subgraph detection has received significant attention recently, with new upper and lower bounds, but several fundamental questions remain open. In this paper we prove new possibility and impossibility results for subgraph detection in the CONGEST model. We show for the first time that some subgraphs require superlinear --- in fact, nearly quadratic --- running time, even in small-diameter networks. We also study cycle-detection, and show that any even cycle can be detected in sublinear time (in contrast to odd cycles, which require linear time). For the special case of triangle-detection, we show that deterministic algorithms require $Ømega(łog n)$ total communication even in graphs of degree 2, and that one-round randomized algorithms must send $Ømega(Δ)$ bits in graphs of degree Δ, improving on the recent results of [Abboud et. al.]. Finally, we extend a recent lower bound of [Izumi, Le Gall] on listing all triangles to cliques of any size.

In this paper we initiate the study of property testing in multi-party communication complexity, focusing on testing triangle-freeness in graphs. We consider the coordinator model, where we have k players receiving private inputs, and a coordinator who receives no input; the coordinator can communicate with all the players, but the players cannot communicate with each other. In this model, we ask: if an input graph is divided between the players, with each player receiving some of the edges, how many bits do the players and the coordinator need to exchange to determine if the graph is triangle-free, or far from triangle-free?

In this paper we present distributed testing algorithms of graph properties in the CONGEST-model [Censor-Hillel et al. 2016]. We present one-sided error testing algorithms in the general graph model. We first describe a general procedure for converting $ε$-testers with a number of rounds $f(D)$, where $D$ denotes the diameter of the graph, to $O((\log n)/ε)+f((\log n)/ε)$ rounds, where $n$ is the number of processors of the network. We then apply this procedure to obtain an optimal tester, in terms of $n$, for testing bipartiteness, whose round complexity is $O(ε^{-1}\log n)$, which improves over the $poly(ε^{-1} \log n)$-round algorithm by Censor-Hillel et al. (DISC 2016). Moreover, for cycle-freeness, we obtain a \emph{corrector} of the graph that locally corrects the graph so that the corrected graph is acyclic. Note that, unlike a tester, a corrector needs to mend the graph in many places in the case that the graph is far from having the property. In the second part of the paper we design algorithms for testing whether the network is $H$-free for any connected $H$ of size up to four with round complexity of $O(ε^{-1})$. This improves over the $O(ε^{-2})$-round algorithms for testing triangle freeness by Censor-Hillel et al. (DISC 2016) and for testing excluded graphs of size $4$ by Fraigniaud et al. (DISC 2016). In the last part we generalize the global tester by Iwama and Yoshida (ITCS 2014) of testing $k$-path freeness to testing the exclusion of any tree of order $k$. We then show how to simulate this algorithm in the CONGEST-model in $O(k^{k^2+1}\cdotε^{-k})$ rounds.

We show that any randomised Monte Carlo distributed algorithm for the Lovász local lemma requires Omega(log log n) communication rounds, assuming that it finds a correct assignment with high probability. Our result holds even in the special case of d = O(1), where d is the maximum degree of the dependency graph. By prior work, there are distributed algorithms for the Lovász local lemma with a running time of O(log n) rounds in bounded-degree graphs, and the best lower bound before our work was Omega(log* n) rounds [Chung et al. 2014].