Fooling views: a new lower bound technique for distributed computations under congestion

DOI10.1007/s00446-020-00373-4zbMath1497.68556arXiv1711.01623OpenAlexW3015570282MaRDI QIDQ2220402

Keren Censor-Hillel, Amir Abboud, Seri Khoury, Christoph Lenzen

Publication date: 22 January 2021

Published in: Distributed Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Related Items (4)

A note on improved results for one round distributed clique listing ⋮ Lower bound for constant-size local certification ⋮ Distributed Testing of Graph Isomorphism in the CONGEST Model. ⋮ The Communication Complexity of Set Intersection and Multiple Equality Testing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An optimal bit complexity randomized distributed MIS algorithm
• On the distributional complexity of disjointness
• An improved combinatorial algorithm for Boolean matrix multiplication
• Distributed testing of excluded subgraphs
• Quantum algorithm for triangle finding in sparse graphs
• Algebraic methods in the congested clique
• On extremal problems of graphs and generalized graphs
• A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction
• Construction and Impromptu Repair of an MST in a Distributed Network with o(m) Communication
• Randomized Proof-Labeling Schemes
• Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• A tight unconditional lower bound on distributed randomwalk computation
• Improved distributed steiner forest construction
• On the power of the congested clique model
• Local Computation
• Powers of tensors and fast matrix multiplication
• Solving the Induced Subgraph Problem in the Randomized Multiparty Simultaneous Messages Model
• A trade-off between information and communication in broadcast protocols
• Finding a Heaviest Vertex-Weighted Triangle Is not Harder than Matrix Multiplication
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
• Locality in Distributed Graph Algorithms
• Finding a Minimum Circuit in a Graph
• Color-coding
• Distributed Computing: A Locality-Sensitive Approach
• If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser
• What Can be Computed Locally?
• Communication Complexity
• Distributed Verification and Hardness of Distributed Approximation
• “Tri, Tri Again”: Finding Triangles and Small Subgraphs in a Distributed Setting
• A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees
• A Simple Deterministic Distributed MST Algorithm with Near-Optimal Time and Message Complexities
• Improved Distributed Expander Decomposition and Nearly Optimal Triangle Enumeration
• Listing Triangles
• Distributed Triangle Detection via Expander Decomposition
• Quantum Algorithms for Element Distinctness
• A lower bound for the distributed Lovász local lemma
• Speeding up the Four Russians Algorithm by About One More Logarithmic Factor
• Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
• Brief Announcement
• Triangle Finding and Listing in CONGEST Networks
• Quantum Algorithms for the Triangle Problem
• Span programs for functions with constant-sized 1-certificates
• Multiplying matrices faster than coppersmith-winograd
• Experimental and Efficient Algorithms
• Improved Quantum Query Algorithms for Triangle Finding and Associativity Testing
• Efficient Triangle Counting in Large Graphs via Degree-Based Vertex Partitioning
• Distributed construction of purely additive spanners
• Fast distributed algorithms for testing graph properties

This page was built for publication: Fooling views: a new lower bound technique for distributed computations under congestion