Fooling views: a new lower bound technique for distributed computations under congestion
From MaRDI portal
Publication:2220402
DOI10.1007/s00446-020-00373-4zbMath1497.68556arXiv1711.01623MaRDI 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
Related Items
The Communication Complexity of Set Intersection and Multiple Equality Testing, Lower bound for constant-size local certification, Distributed Testing of Graph Isomorphism in the CONGEST Model., A note on improved results for one round distributed clique listing
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
