Fooling views: a new lower bound technique for distributed computations under congestion (Q2220402): Difference between revisions

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