Algebraic methods in the congested clique
From MaRDI portal
Publication:2010605
DOI10.1007/s00446-016-0270-2zbMath1452.68267arXiv1503.04963MaRDI QIDQ2010605
Jukka Suomela, Janne H. Korhonen, Keren Censor-Hillel, Christoph Lenzen, Petteri Kaski, Ami Paz
Publication date: 27 November 2019
Published in: Distributed Computing, Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1503.04963
lower bounds; distributed computing; matrix multiplication; distance computation; congested clique model; subgraph detection
68Q25: Analysis of algorithms and problem complexity
68W40: Analysis of algorithms
68W30: Symbolic computation and algebraic computation
68R10: Graph theory (including graph drawing) in computer science
05C38: Paths and cycles
05C12: Distance in graphs
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68W25: Approximation algorithms
68W15: Distributed algorithms
Related Items
Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models, A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths, Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time, The Impact of Locality in the Broadcast Congested Clique Model, Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths, Fast distributed algorithms for testing graph properties, Distributed Approximation Algorithms for Steiner Tree in the CONGESTED CLIQUE, On the power of threshold-based algorithms for detecting cycles in the \textsc{CONGEST} model, On the power of threshold-based algorithms for detecting cycles in the CONGEST model, Bounds on oblivious multiparty quantum communication complexity, Brief Announcement: The Laplacian Paradigm in Deterministic Congested Clique, Lessons from the congested clique applied to MapReduce, Algebraic methods in the congested clique, The role of randomness in the broadcast congested clique model, Fast approximate shortest paths in the congested clique, Near-optimal scheduling in the congested clique, Approximate minimum directed spanning trees under congestion, Sublinear-time distributed algorithms for detecting small cliques and even cycles, Single-source shortest paths in the CONGEST model with improved bounds, Graph reconstruction in the congested clique, Derandomizing local distributed algorithms under bandwidth restrictions, Detecting cliques in CONGEST networks, Fooling views: a new lower bound technique for distributed computations under congestion, Sparse matrix multiplication and triangle listing in the congested clique model, A distributed algorithm for directed minimum-weight spanning tree, The Effect of Range and Bandwidth on the Round Complexity in the Congested Clique Model, Sparsifying Congested Cliques and Core-Periphery Networks, Deterministic Subgraph Detection in Broadcast CONGEST., Lower Bounds for Subgraph Detection in the CONGEST Model
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Faster algorithms for finding and counting subgraphs
- Finding and counting given length cycles
- On the complexity of fixed parameter clique and dominating set
- A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths
- Communication complexity of PRAMs
- An \(O(n^{3}(\log\log n /\log n )^{5/4})\) time algorithm for all pairs shortest path
- On the all-pairs-shortest-path problem in unweighted undirected graphs.
- Finding paths of length \(k\) in \(O^{*}(2^k)\) time
- An \(O(n^{3}\log \log n/\log n)\) time algorithm for the all-pairs shortest path problem
- An algorithm for finding all shortest paths using \(N^{2\cdot 81}\) infinite-precision multiplications
- Communication lower bounds for distributed-memory matrix multiplication
- Computer science today. Recent trends and developments
- Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
- Algebraic methods in the congested clique
- All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
- Gaussian elimination is not optimal
- Efficient determination of the transitive closure of a directed graph
- A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction
- Toward Optimal Bounds in the Congested Clique
- Finding, Minimizing, and Counting Weighted Subgraphs
- Saving space by algebraization
- An O(n 3 loglogn/log2 n) Time Algorithm for All Pairs Shortest Paths
- Optimal distributed all pairs shortest paths and applications
- The round complexity of distributed sorting
- On the power of the congested clique model
- Probably optimal graph motifs
- More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
- Distributed Algorithms for Network Diameter and Girth
- Powers of tensors and fast matrix multiplication
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- Faster Algebraic Algorithms for Path and Packing Problems
- Fourier meets M\"{o}bius: fast subset convolution
- Set Partitioning via Inclusion-Exclusion
- New Bounds on the Complexity of the Shortest Path Problem
- Finding a Minimum Circuit in a Graph
- Fast Distributed Construction of Smallk-Dominating Sets and Applications
- Color-coding
- Distributed Computing: A Locality-Sensitive Approach
- Counting Thin Subgraphs via Packings Faster than Meet-in-the-Middle Time
- Fast Hamiltonicity Checking Via Bases of Perfect Matchings
- Memorization and Association on a Realistic Neural Model
- Computing and Combinatorics
- “Tri, Tri Again”: Finding Triangles and Small Subgraphs in a Distributed Setting
- Graph Expansion Analysis for Communication Costs of Fast Rectangular Matrix Multiplication
- Shortest Two Disjoint Paths in Polynomial Time
- Optimal deterministic routing and sorting on the congested clique
- Efficient distributed source detection with limited bandwidth
- Distributed approximation algorithms for weighted shortest paths
- Faster all-pairs shortest paths via circuit complexity
- Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth
- Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms
- Graph expansion and communication costs of fast matrix multiplication
- Determinant Sums for Undirected Hamiltonicity
- Tight bounds for parallel randomized load balancing
- Distributed verification and hardness of distributed approximation
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Fast routing table construction using small messages
- Lessons from the Congested Clique Applied to MapReduce
- Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
- Bulk-synchronous parallel Gaussian elimination
