Algebraic Methods in the Congested Clique

Abstract

In this work, we use algebraic methods for studying distance computation and subgraph detection tasks in the congested clique model. Specifically, we adapt parallel matrix multiplication implementations to the congested clique, obtaining an $O(n^{1-2/\omega })$ round matrix multiplication algorithm, where $\omega <2.3728639$ is the exponent of matrix multiplication. In conjunction with known techniques from centralised algorithmics, this gives significant improvements over previous best upper bounds in the congested clique model. The highlight results include: -- triangle and 4-cycle counting in $O(n^{0.158})$ rounds, improving upon the $O(n^{1/3})$ triangle detection algorithm of Dolev et al. [DISC 2012], -- a $(1+o(1))$-approximation of all-pairs shortest paths in $O(n^{0.158})$ rounds, improving upon the $\tilde{O}(n^{1/2})$-round $(2+o(1))$-approximation algorithm of Nanongkai [STOC 2014], and -- computing the girth in $O(n^{0.158})$ rounds, which is the first non-trivial solution in this model. In addition, we present a novel constant-round combinatorial algorithm for detecting 4-cycles.

This is work is a merger of arxiv:1412.2109 and arxiv:1412.2667

References in corpus (4)

• Algebraic Methods in the Congested Clique
• Tight Bounds for Parallel Randomized Load Balancing
• Lessons from the Congested Clique Applied to MapReduce
• Minimum-weight Spanning Tree Construction in $O(\log \log \log n)$ Rounds on the Congested Clique

Cited by in corpus (21)

• Algebraic Methods in the Congested Clique
• A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths
• Triangle Finding and Listing in CONGEST Networks
• On Distributed Listing of Cliques
• Tight Distributed Listing of Cliques
• Deterministic subgraph detection in broadcast CONGEST
• Distributed Algorithms for Directed Betweenness Centrality and All Pairs Shortest Paths
• Distributed Subgraph Detection
• Distributed Property Testing for Subgraph-Freeness Revisited
• Bounds on oblivious multiparty quantum communication complexity
• Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
• Universally-Optimal Distributed Shortest Paths and Transshipment via Graph-Based L1-Oblivious Routing
• Distributed Testing of Excluded Subgraphs
• Fast Distributed Algorithms for Testing Graph Properties
• On The Multiparty Communication Complexity of Testing Triangle-Freeness
• Fast Distributed Algorithms for Connectivity and MST in Large Graphs
• Broadcast Congested Clique: Planted Cliques and Pseudorandom Generators
• Lower Bounds for Induced Cycle Detection in Distributed Computing
• Beyond Distributed Subgraph Detection: Induced Subgraphs, Multicolored Problems and Graph Parameters
• Algorithms for Noisy Broadcast under Erasures
• Superlinear Lower Bounds for Distributed Subgraph Detection