Publication:2010605

DOI10.1007/s00446-016-0270-2zbMath1452.68267arXiv1503.04963OpenAlexW2950813619MaRDI 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

zbMATH Keywords

lower boundsdistributed computingmatrix multiplicationdistance computationcongested clique modelsubgraph detection

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Symbolic computation and algebraic computation (68W30) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Distributed algorithms (68W15)

Related Items (33)

Sublinear-time distributed algorithms for detecting small cliques and even cycles ⋮ Single-source shortest paths in the CONGEST model with improved bounds ⋮ Deterministic Subgraph Detection in Broadcast CONGEST. ⋮ Lower Bounds for Subgraph Detection in the CONGEST Model ⋮ Graph reconstruction in the congested clique ⋮ Derandomizing local distributed algorithms under bandwidth restrictions ⋮ Lessons from the congested clique applied to MapReduce ⋮ 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 ⋮ Unnamed Item ⋮ A distributed algorithm for directed minimum-weight spanning tree ⋮ Brief Announcement: The Laplacian Paradigm in Deterministic Congested Clique ⋮ Detecting cliques in CONGEST networks ⋮ Fooling views: a new lower bound technique for distributed computations under congestion ⋮ Algebraic methods in the congested clique ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Fast distributed algorithms for testing graph properties ⋮ Sparse matrix multiplication and triangle listing in the congested clique model ⋮ The role of randomness in the broadcast congested clique model ⋮ The Impact of Locality in the Broadcast Congested Clique Model ⋮ The Effect of Range and Bandwidth on the Round Complexity in the Congested Clique Model ⋮ Fast approximate shortest paths in the congested clique ⋮ Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths ⋮ Sparsifying Congested Cliques and Core-Periphery Networks ⋮ 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 Approximation Algorithms for Steiner Tree in the CONGESTED CLIQUE ⋮ Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time ⋮ Near-optimal scheduling in the congested clique ⋮ Approximate minimum directed spanning trees under congestion

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

This page was built for publication: Algebraic methods in the congested clique