An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model (Q4620411): Difference between revisions

@@ Property / Wikidata QID @@
+Q115525618
@@ Property / Wikidata QID: Q115525618 / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+A Distributed (2 + ε)-Approximation for Vertex Cover in O(log Δ / ε log log Δ) Rounds
+Normal rank
@@ Property / cites work @@
+Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
+Normal rank
@@ Property / cites work @@
+Locally-Iterative Distributed (Δ+ 1)
@@ Property / cites work: Locally-Iterative Distributed (Δ+ 1) / rank @@
+Normal rank
@@ Property / cites work @@
+Distributed $(\Delta+1)$-Coloring in Linear (in $\Delta$) Time
+Normal rank
@@ Property / cites work @@
+The Locality of Distributed Symmetry Breaking
@@ Property / cites work: The Locality of Distributed Symmetry Breaking / rank @@
+Normal rank
@@ Property / cites work @@
+Chromatic number, girth and maximal degree
@@ Property / cites work: Chromatic number, girth and maximal degree / rank @@
+Normal rank
@@ Property / cites work @@
+Q3852212
@@ Property / cites work: Q3852212 / rank @@
+Normal rank
@@ Property / cites work @@
+A lower bound for the distributed Lovász local lemma
+Normal rank
@@ Property / cites work @@
+Q4608064
@@ Property / cites work: Q4608064 / rank @@
+Normal rank
@@ Property / cites work @@
+An optimal distributed (Δ+1)-coloring algorithm?
@@ Property / cites work: An optimal distributed (Δ+1)-coloring algorithm? / rank @@
+Normal rank
@@ Property / cites work @@
+Distributed algorithms for the Lovász local lemma and graph coloring
+Normal rank
@@ Property / cites work @@
+Regular graphs of large girth and arbitrary degree
+Normal rank
@@ Property / cites work @@
+(2Δ — l)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting
+Normal rank
@@ Property / cites work @@
+Impossibility of distributed consensus with one faulty process
+Normal rank
@@ Property / cites work @@
+Q2959048
@@ Property / cites work: Q2959048 / rank @@
+Normal rank
@@ Property / cites work @@
+An Improved Distributed Algorithm for Maximal Independent Set
+Normal rank
@@ Property / cites work @@
+Distributed Degree Splitting, Edge Coloring, and Orientations
+Normal rank
@@ Property / cites work @@
+Distributed (Δ +1)-Coloring in Sublogarithmic Rounds
+Normal rank
@@ Property / cites work @@
+Byzantine agreement in polynomial expected time
@@ Property / cites work: Byzantine agreement in polynomial expected time / rank @@
+Normal rank
@@ Property / cites work @@
+Proof labeling schemes
@@ Property / cites work: Proof labeling schemes / rank @@
+Normal rank
@@ Property / cites work @@
+Toward more localized local algorithms: removing assumptions concerning global knowledge
+Normal rank
@@ Property / cites work @@
+Super-Fast 3-Ruling Sets.
@@ Property / cites work: Super-Fast 3-Ruling Sets. / rank @@
+Normal rank
@@ Property / cites work @@
+Local Computation
@@ Property / cites work: Local Computation / 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 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 @@
+Some simple distributed algorithms for sparse networks
+Normal rank
@@ Property / cites work @@
+On the Complexity of Distributed Network Decomposition
+Normal rank
@@ Property / cites work @@
+Distributed coloring algorithms for triangle-free graphs
+Normal rank
@@ Property / cites work @@
+An optimal maximal independent set algorithm for bounded-independence graphs
+Normal rank
@@ Property / cites work @@
+Q3392275
@@ Property / cites work: Q3392275 / rank @@
+Normal rank
@@ Property / cites work @@
+Improved deterministic distributed matching via rounding
+Normal rank
@@ Property / cites work @@
+Sublogarithmic distributed algorithms for Lovász local lemma, and the complexity hierarchy
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1137/17m1117537
+Normal rank
@@ Property / OpenAlex ID @@
+W2913663107
@@ Property / OpenAlex ID: W2913663107 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:4620411