Fooling views: a new lower bound technique for distributed computations under congestion
From MaRDI portal
Publication:2220402
Abstract: We introduce a novel lower bound technique for distributed graph algorithms under bandwidth limitations. We define the notion of emph{fooling views} and exemplify its strength by proving two new lower bounds for triangle membership in the CONGEST(B) model: (i) Any -round algorithm requires for a constant . (ii) If , even in constant-degree graphs any algorithm must take rounds. The implication of the former is the first proven separation between the LOCAL and the CONGEST models for deterministic triangle membership. The latter result is the first non-trivial lower bound on the number of rounds required, even for emph{triangle detection}, under limited bandwidth. All previous known techniques are provably incapable of giving these bounds. We hope that our approach may pave the way for proving lower bounds for additional problems in various settings of distributed computing for which previous techniques do not suffice.
Recommendations
- scientific article; zbMATH DE number 1696663
- Distributed Computing
- A lower bound for probabilistic distributed algorithms
- Lower Bounds for Distributed Maximum-Finding Algorithms
- Near-constant-time distributed algorithms on a congested clique
- Two lower bounds in asynchronous distributed computation
- Optimal lower bounds for some distributed algorithms for a complete network of processors
- Derandomizing local distributed algorithms under bandwidth restrictions
- Derandomizing local distributed algorithms under bandwidth restrictions
Cites work
- ``Tri, tri again: finding triangles and small subgraphs in a distributed setting (extended abstract)
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- A lower bound for the distributed Lovász local lemma
- A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
- A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A tight unconditional lower bound on distributed randomwalk computation
- A trade-off between information and communication in broadcast protocols
- An optimal bit complexity randomized distributed MIS algorithm
- Brief announcement: Symmetry breaking in the \textsc{Congest} model: time- and message-efficient algorithms for ruling sets
- Color-coding
- Communication Complexity
- Construction and impromptu repair of an MST in a distributed network with o(m) communication
- Distributed Computing: A Locality-Sensitive Approach
- Distributed testing of excluded subgraphs
- Distributed triangle detection via expander decomposition
- Distributed verification and hardness of distributed approximation
- Efficient triangle counting in large graphs via degree-based vertex partitioning
- Experimental and Efficient Algorithms
- Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication
- Finding a Minimum Circuit in a Graph
- Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
- scientific article; zbMATH DE number 1324671 (Why is no real title available?)
- If the current clique algorithms are optimal, so is Valiant's parser
- Improved distributed expander decomposition and nearly optimal triangle enumeration
- Improved distributed Steiner forest construction
- Improved quantum query algorithms for triangle finding and associativity testing
- Listing triangles
- Local computation: lower and upper bounds
- Locality in Distributed Graph Algorithms
- Matching triangles and basing hardness on an extremely popular conjecture
- Multiparty quantum communication complexity of triangle finding
- Multiplying matrices faster than coppersmith-winograd
- Networks cannot compute their diameter in sublinear time
- On extremal problems of graphs and generalized graphs
- On the distributional complexity of disjointness
- On the power of the congested clique model
- Powers of tensors and fast matrix multiplication
- Quadratic and near-quadratic lower bounds for the CONGEST model
- Quantum Algorithms for Element Distinctness
- Quantum Algorithms for the Triangle Problem
- Randomized proof-labeling schemes
- Regularity lemmas and combinatorial algorithms
- Solving the \textsc{induced subgraph} problem in the randomized multiparty simultaneous messages model
- Span programs for functions with constant-sized 1-certificates (extended abstract)
- Speeding up the four Russians algorithm by about one more logarithmic factor
- The randomized communication complexity of set disjointness
- Triangle Finding and Listing in CONGEST Networks
- Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
- What Can be Computed Locally?
Cited in
(8)- A note on improved results for one round distributed clique listing
- Does Preprocessing Help under Congestion?
- The communication complexity of set intersection and multiple equality testing
- Distributed Testing of Graph Isomorphism in the CONGEST Model.
- Improved hardness of approximation of diameter in the CONGEST model
- Deterministic near-optimal distributed listing of cliques
- The message complexity of distributed graph optimization
- Distributed subgraph finding: progress and challenges (invited talk)
This page was built for publication: Fooling views: a new lower bound technique for distributed computations under congestion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2220402)
