Sparse matrix multiplication and triangle listing in the congested clique model

DOI10.1016/j.tcs.2019.11.006zbMath1447.68015arXiv1802.04789WikidataQ126823607 ScholiaQ126823607MaRDI QIDQ2290622

Keren Censor-Hillel, Elia Turner, Dean Leitersdorf

Publication date: 29 January 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1802.04789

zbMATH Keywords

distributed algorithms; matrix multiplication; congested clique; triangle listing

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68W15: Distributed algorithms

Related Items

Unnamed Item, Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time, Hamming Distance Completeness, Fast approximate shortest paths in the congested clique

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding and counting given length cycles
• Matrix multiplication via arithmetic progressions
• Further algebraic algorithms in the congested clique model and applications to graph-theoretic problems
• Algebraic methods in the congested clique
• Gaussian elimination is not optimal
• Exploiting Multiple Levels of Parallelism in Sparse Matrix-Matrix Multiplication
• On the power of the congested clique model
• Fast sparse matrix multiplication
• Parallel Sparse Matrix-Matrix Multiplication and Indexing: Implementation and Experiments
• Powers of tensors and fast matrix multiplication
• Two Fast Algorithms for Sparse Matrices: Multiplication and Permuted Transposition
• “Tri, Tri Again”: Finding Triangles and Small Subgraphs in a Distributed Setting
• Optimal deterministic routing and sorting on the congested clique
• Distributed approximation algorithms for weighted shortest paths
• Distributed Computation of Large-scale Graph Problems
• Triangle Finding and Listing in CONGEST Networks
• Multiplying matrices faster than coppersmith-winograd