On the public citation graph
A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
0 signed · 107 inferred · view as graph
Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.
Is this your work? Sign in with ORCID and put your name on the
claims that are yours.
Reference health. See whether every reference in this work resolves to a
known work and none has been retracted — and get a dated CiteStamped
badge you can embed.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1016/s0019-9958(86)80023-7openalex-snapshot
Deterministic coin tossing with applications to optimal parallel list ranking
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1007/978-1-4939-2864-4_608openalex-snapshot
Locality in Distributed Graph Algorithms
inferred← citeshttps://doi.org/10.1007/978-3-030-24922-9_3openalex-snapshot
Locality of Not-so-Weak Coloring
inferred← citeshttps://doi.org/10.1007/978-3-030-28796-2_15openalex-snapshot
Localisation-Resistant Random Words with Small Alphabets
inferred← citeshttps://doi.org/10.1007/978-3-031-32733-9_15openalex-snapshot
Distributed Half-Integral Matching and Beyond
inferred← citeshttps://doi.org/10.1007/978-3-319-25258-2_4openalex-snapshot
Exact Bounds for Distributed Graph Colouring
inferred← citeshttps://doi.org/10.1007/978-3-319-48314-6openalex-snapshot
Structural Information and Communication Complexity
inferred← citeshttps://doi.org/10.1007/978-3-319-72050-0_16openalex-snapshot
How Long It Takes for an Ordinary Node with an Ordinary ID to Output?
inferred← citeshttps://doi.org/10.1007/978-3-540-73420-8_22openalex-snapshot
Distributed Computing with Advice: Information Sensitivity of Graph Coloring
inferred← citeshttps://doi.org/10.1007/978-3-540-87779-0_27openalex-snapshot
Leveraging Linial’s Locality Limit
inferred← citeshttps://doi.org/10.1007/978-3-540-87779-0_6openalex-snapshot
Fast Distributed Approximations in Planar Graphs
inferred← citeshttps://doi.org/10.1007/978-3-540-87779-0_7openalex-snapshot
Closing the Complexity Gap between FCFS Mutual Exclusion and Mutual Exclusion
inferred← citeshttps://doi.org/10.1007/978-3-642-04355-0_26openalex-snapshot
What Can Be Observed Locally?
inferred← citeshttps://doi.org/10.1007/978-3-642-27848-8_608-1openalex-snapshot
Locality in Distributed Graph Algorithms
inferred← citeshttps://doi.org/10.1007/978-3-642-33651-5_26openalex-snapshot
Randomized Distributed Decision
inferred← citeshttps://doi.org/10.1007/s00446-008-0076-yopenalex-snapshot
Distributed computing with advice: information sensitivity of graph coloring
inferred← citeshttps://doi.org/10.1007/s00446-013-0186-zopenalex-snapshot
Distributed minimum dominating set approximations in restricted families of graphs
inferred← citeshttps://doi.org/10.1007/s00446-014-0211-xopenalex-snapshot
Randomized distributed decision
inferred← citeshttps://doi.org/10.1007/s00446-014-0225-4openalex-snapshot
Tight bounds for parallel randomized load balancing
inferred← citeshttps://doi.org/10.1007/s00446-020-00373-4openalex-snapshot
Fooling views: a new lower bound technique for distributed computations under congestion
inferred← citeshttps://doi.org/10.1007/s00446-022-00435-9openalex-snapshot
Locally checkable problems in rooted trees
inferred← citeshttps://doi.org/10.1007/s00446-023-00453-1openalex-snapshot
Node and edge averaged complexities of local graph problems
inferred← citeshttps://doi.org/10.1016/j.tcs.2019.01.023openalex-snapshot
How long it takes for an ordinary node with an ordinary id to output?
inferred← citeshttps://doi.org/10.1016/j.tcs.2023.114278openalex-snapshot
Distributed half-integral matching and beyond
inferred← citeshttps://doi.org/10.1017/s0963548300000857openalex-snapshot
Local-Global Phenomena in Graphs
inferred← citeshttps://doi.org/10.1098/rsta.2011.0212openalex-snapshot
Distributed algorithms for sensor networks
inferred← citeshttps://doi.org/10.1109/focs.2016.72openalex-snapshot
An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model
inferred← citeshttps://doi.org/10.1109/focs.2017.23openalex-snapshot
A Time Hierarchy Theorem for the LOCAL Model
inferred← citeshttps://doi.org/10.1109/focs.2019.00037openalex-snapshot
Lower Bounds for Maximal Matchings and Maximal Independent Sets
inferred← citeshttps://doi.org/10.1109/focs.2019.00097openalex-snapshot
Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds
inferred← citeshttps://doi.org/10.1109/focs46700.2020.00042openalex-snapshot
Distributed Lower Bounds for Ruling Sets
inferred← citeshttps://doi.org/10.1109/istcs.1995.377023openalex-snapshot
Local computations on static and dynamic graphs
inferred← citeshttps://doi.org/10.1137/06065310xopenalex-snapshot
A Primal-Dual Bicriteria Distributed Algorithm for Capacitated Vertex Cover
inferred← citeshttps://doi.org/10.1137/1.9781611975994.76openalex-snapshot
Faster Deterministic Distributed Coloring Through Recursive List Coloring
inferred← citeshttps://doi.org/10.1137/1.9781611977554.ch163openalex-snapshot
Improved Distributed Algorithms for the Lovász Local Lemma and Edge Coloring
inferred← citeshttps://doi.org/10.1137/17m1117537openalex-snapshot
An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model
inferred← citeshttps://doi.org/10.1137/17m1157957openalex-snapshot
A Time Hierarchy Theorem for the LOCAL Model
inferred← citeshttps://doi.org/10.1137/19m1249527openalex-snapshot
Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering
inferred← citeshttps://doi.org/10.1137/s0097539793254571openalex-snapshot
What Can be Computed Locally?
inferred← citeshttps://doi.org/10.1137/s0895480100373121openalex-snapshot
On the Distributed Complexity of Computing Maximal Matchings
inferred← citeshttps://doi.org/10.1145/1281100.1281111openalex-snapshot
A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
inferred← citeshttps://doi.org/10.1145/1993636.1993639openalex-snapshot
Tight bounds for parallel randomized load balancing
inferred← citeshttps://doi.org/10.1145/2332432.2332465openalex-snapshot
Lower bounds for local approximation
inferred← citeshttps://doi.org/10.1145/2484239.2501983openalex-snapshot
Optimal deterministic routing and sorting on the congested clique
inferred← citeshttps://doi.org/10.1145/2499228openalex-snapshot
Towards a complexity theory for local distributed computing
inferred← citeshttps://doi.org/10.1145/2755573.2755596openalex-snapshot
Randomized Local Network Computing
inferred← citeshttps://doi.org/10.1145/2897518.2897570openalex-snapshot
A lower bound for the distributed Lovász local lemma
inferred← citeshttps://doi.org/10.1145/301308.301360openalex-snapshot
A faster distributed algorithm for computing maximal matchings deterministically
inferred← citeshttps://doi.org/10.1145/3178120openalex-snapshot
Distributed (Δ +1)-Coloring in Sublogarithmic Rounds
inferred← citeshttps://doi.org/10.1145/3188745.3188964openalex-snapshot
An optimal distributed (Δ+1)-coloring algorithm?
inferred← citeshttps://doi.org/10.1145/3293611.3331605openalex-snapshot
Hardness of Minimal Symmetry Breaking in Distributed Computing
inferred← citeshttps://doi.org/10.1145/3293611.3331606openalex-snapshot
The Distributed Complexity of Locally Checkable Problems on Paths is Decidable
inferred← citeshttps://doi.org/10.1145/3365004openalex-snapshot
Distributed Edge Coloring and a Special Case of the Constructive Lovász Local Lemma
inferred← citeshttps://doi.org/10.1145/3382734.3405694openalex-snapshot
Brief Announcement: Round eliminator: a tool for automatic speedup simulation
inferred← citeshttps://doi.org/10.1145/3382734.3405715openalex-snapshot
How much does randomness help with locally checkable problems?
inferred← citeshttps://doi.org/10.1145/3382734.3405721openalex-snapshot
Seeing Far vs. Seeing Wide: Volume Complexity of Local Graph Problems
inferred← citeshttps://doi.org/10.1145/3382734.3405745openalex-snapshot
Truly Tight-in-Δ Bounds for Bipartite Maximal Matching and Variants
inferred← citeshttps://doi.org/10.1145/3409964.3461785openalex-snapshot
Efficient Load-Balancing through Distributed Token Dropping
inferred← citeshttps://doi.org/10.1145/3409964.3461804openalex-snapshot
Distributed Graph Coloring Made Easy
inferred← citeshttps://doi.org/10.1145/3427361.3427374openalex-snapshot
Using Round Elimination to Understand Locality
inferred← citeshttps://doi.org/10.1145/3461458openalex-snapshot
Lower Bounds for Maximal Matchings and Maximal Independent Sets
inferred← citeshttps://doi.org/10.1145/3465084.3467901openalex-snapshot
Improved Distributed Lower Bounds for MIS and Bounded (Out-)Degree Dominating Sets in Trees
inferred← citeshttps://doi.org/10.1145/3465084.3467909openalex-snapshot
Can We Break Symmetry with o(m) Communication?
inferred← citeshttps://doi.org/10.1145/3465084.3467934openalex-snapshot
Locally Checkable Problems in Rooted Trees
inferred← citeshttps://doi.org/10.1145/3470640openalex-snapshot
Randomized Local Network Computing: Derandomization Beyond Locally Checkable Labelings
inferred← citeshttps://doi.org/10.1145/3490148.3538566openalex-snapshot
Average Awake Complexity of MIS and Matching
inferred← citeshttps://doi.org/10.1145/3519270.3538419openalex-snapshot
Node and Edge Averaged Complexities of Local Graph Problems
inferred← citeshttps://doi.org/10.1145/3519270.3538452openalex-snapshot
The Landscape of Distributed Complexities on Trees and Beyond
inferred← citeshttps://doi.org/10.1145/3519935.3520023openalex-snapshot
Near-optimal distributed degree+1 coloring
inferred← citeshttps://doi.org/10.1145/3519935.3520027openalex-snapshot
Distributed ∆-coloring plays hide-and-seek
inferred← citeshttps://doi.org/10.1145/3558481.3591319openalex-snapshot
Brief Announcement: List Defective Colorings: Distributed Algorithms and Applications
inferred← citeshttps://doi.org/10.1145/3732772.3733547openalex-snapshot
Nearly-Optimal Distributed Ruling Sets for Trees and high-girth graphs
inferred← citeshttps://doi.org/10.1145/3796701.3815908openalex-snapshot
Brief Announcement: Is a LOCAL Algorithm Computable?
inferred← citeshttps://doi.org/10.1145/3798129.3800899openalex-snapshot
Sublogarithmic Distributed Vertex Coloring with Optimal Number of Colors
inferred← citeshttps://doi.org/10.1145/3819817openalex-snapshot
Distributed Δ-Coloring Plays Hide-and-Seek
inferred← citeshttps://doi.org/10.1201/9781351236423-12openalex-snapshot
Distributed Approximation Algorithms via LP-Duality and Randomization
inferred← citeshttps://doi.org/10.1214/15-aihp735openalex-snapshot
One-dependent coloring by finitary factors
inferred← citeshttps://doi.org/10.1214/19-aop1363openalex-snapshot
Mallows permutations and finite dependence
inferred← citeshttps://doi.org/10.1214/19-aop1417openalex-snapshot
Finitely dependent processes are finitary
inferred← citeshttps://doi.org/10.1214/24-ecp600openalex-snapshot
Symmetrization for finitely dependent colouring
inferred← citeshttps://doi.org/10.2200/s00520ed1v01y201307dct011openalex-snapshot
Distributed Graph Coloring: Fundamentals and Recent Developments
inferred← citeshttps://doi.org/10.3929/ethz-a-005752807openalex-snapshot
On locality and related problems: Communicating, computing, exploring
inferred← citeshttps://doi.org/10.3929/ethz-a-006517282openalex-snapshot
Synchronization and symmetry breaking in distributed systems
inferred← citeshttps://doi.org/10.4230/lipics.disc.2020.17openalex-snapshot
Classification of Distributed Binary Labeling Problems
inferred← citeshttps://doi.org/10.48550/arxiv.0903.1133openalex-snapshot
What Can be Observed Locally? Round-based Models for Quantum Distributed Computing
inferred← citeshttps://doi.org/10.48550/arxiv.1102.5425openalex-snapshot
Tight Bounds for Parallel Randomized Load Balancing
inferred← citeshttps://doi.org/10.48550/arxiv.1207.0252openalex-snapshot
Randomized Distributed Decision
inferred← citeshttps://doi.org/10.48550/arxiv.1207.1852openalex-snapshot
Optimal Deterministic Routing and Sorting on the Congested Clique
inferred← citeshttps://doi.org/10.48550/arxiv.1502.04963openalex-snapshot
Exact bounds for distributed graph colouring
inferred← citeshttps://doi.org/10.48550/arxiv.1602.08166openalex-snapshot
An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model
inferred← citeshttps://doi.org/10.48550/arxiv.1704.05739openalex-snapshot
How Long It Takes for an Ordinary Node with an Ordinary ID to Output?
inferred← citeshttps://doi.org/10.48550/arxiv.1708.04290openalex-snapshot
Distributed Edge Coloring with Small Palettes and a Special Case of the Constructive Lovász Local Lemma
inferred← citeshttps://doi.org/10.5555/314613.314705openalex-snapshot
On the distributed complexity of computing maximal matchings
inferred← citeshttps://doi.org/10.70675/8a31edd0z6c6cz4167za099zc7947720d54dopenalex-snapshot
Questions de localisabilité pour le calcul distribué
inferred← citeshttps://doi.org/10.7146/brics.v4i38.18964openalex-snapshot
On the Distributed Complexity of Computing Maximal Matchings
Editorial review for independent work. ICSAC — the Institute for Complexity
Science and Advanced Computing — runs a structured editorial panel for researchers
publishing outside journals, and publishes on CiteStamp rails. Submission is free
and goes through ORCID: icsacinstitute.org/submit.