On the public citation graph
Smaller Cuts, Higher Lower Bounds
0 signed · 106 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.1006/jagm.1994.1036openalex-snapshot
A Primal-Dual Parallel Approximation Technique Applied to Weighted Set and Vertex Covers
inferredcites →https://doi.org/10.1007/11533719_85openalex-snapshot
Distributed Weighted Vertex Cover via Maximal Matchings
inferredcites →https://doi.org/10.1007/978-3-319-96151-4_9openalex-snapshot
Approximating the Caro-Wei Bound for Independent Sets in Graph Streams
inferredcites →https://doi.org/10.1007/978-3-540-73420-8_62openalex-snapshot
Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners
inferredcites →https://doi.org/10.1007/978-3-540-75520-3_55openalex-snapshot
Estimating Clustering Indexes in Data Streams
inferredcites →https://doi.org/10.1007/978-3-540-87779-0_27openalex-snapshot
Leveraging Linial’s Locality Limit
inferredcites →https://doi.org/10.1007/978-3-540-87779-0_6openalex-snapshot
Fast Distributed Approximations in Planar Graphs
inferredcites →https://doi.org/10.1007/978-3-642-02930-1_27openalex-snapshot
Graph Sparsification in the Semi-streaming Model
inferredcites →https://doi.org/10.1007/978-3-642-03685-9openalex-snapshot
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
inferredcites →https://doi.org/10.1007/978-3-642-04355-0_21openalex-snapshot
A Local 2-Approximation Algorithm for the Vertex Cover Problem
inferredcites →https://doi.org/10.1007/978-3-642-22212-2_22openalex-snapshot
Distributed Coloring Depending on the Chromatic Number or the Neighborhood Growth
inferredcites →https://doi.org/10.1007/978-3-642-23719-5_57openalex-snapshot
Approximate Counting of Cycles in Streams
inferredcites →https://doi.org/10.1007/978-3-642-31585-5_37openalex-snapshot
On the Locality of Some NP-Complete Problems
inferredcites →https://doi.org/10.1007/978-3-642-31585-5_58openalex-snapshot
Distributed Algorithms for Network Diameter and Girth
inferredcites →https://doi.org/10.1007/978-3-642-31594-7_38openalex-snapshot
Streaming and Communication Complexity of Clique Approximation
inferredcites →https://doi.org/10.1007/978-3-662-53426-7_3openalex-snapshot
Near-Linear Lower Bounds for Distributed Distance Computations, Even in Sparse Networks
inferredcites →https://doi.org/10.1007/pl00008932openalex-snapshot
Some simple distributed algorithms for sparse networks
inferredcites →https://doi.org/10.1007/s00224-012-9396-1openalex-snapshot
Spectral Sparsification in the Semi-streaming Setting
inferredcites →https://doi.org/10.1007/s00446-008-0070-4openalex-snapshot
Coloring unstructured radio networks
inferredcites →https://doi.org/10.1007/s00446-008-0076-yopenalex-snapshot
Distributed computing with advice: information sensitivity of graph coloring
inferredcites →https://doi.org/10.1007/s00446-013-0203-2openalex-snapshot
Combinatorial algorithms for distributed graph coloring
inferredcites →https://doi.org/10.1007/s00446-017-0306-2openalex-snapshot
Distributed construction of purely additive spanners
inferredcites →https://doi.org/10.1007/s00453-015-0051-5openalex-snapshot
Streaming Algorithms for Independent Sets in Sparse Hypergraphs
inferredcites →https://doi.org/10.1007/s00453-017-0277-5openalex-snapshot
New Bounds for the CLIQUE-GAP Problem Using Graph Decomposition Theory
inferredcites →https://doi.org/10.1016/0304-3975(92)90260-mopenalex-snapshot
On the distributional complexity of disjointness
inferredcites →https://doi.org/10.1016/j.ic.2014.12.018openalex-snapshot
Distributed coloring algorithms for triangle-free graphs
inferredcites →https://doi.org/10.1016/j.ipl.2007.11.001openalex-snapshot
Streaming algorithm for graph spanners—single pass and constant processing time per edge
inferredcites →https://doi.org/10.1016/j.ipl.2009.02.017openalex-snapshot
A simple local 3-approximation algorithm for vertex cover
inferredcites →https://doi.org/10.1016/j.ipl.2017.12.010openalex-snapshot
A note on hardness of diameter approximation
inferredcites →https://doi.org/10.1016/j.tcs.2005.09.013openalex-snapshot
On graph problems in a semi-streaming model
inferredcites →https://doi.org/10.1016/s0019-9958(86)80023-7openalex-snapshot
Deterministic coin tossing with applications to optimal parallel list ranking
inferredcites →https://doi.org/10.1109/focs.2016.72openalex-snapshot
An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model
inferredcites →https://doi.org/10.1109/focs.2017.23openalex-snapshot
A Time Hierarchy Theorem for the LOCAL Model
inferredcites →https://doi.org/10.1109/focs.2017.24openalex-snapshot
Distributed Exact Weighted All-Pairs Shortest Paths in Õ(n^{5/4}) Rounds
inferredcites →https://doi.org/10.1109/icdm.2008.109openalex-snapshot
Mining Large Networks with Subgraph Counting
inferredcites →https://doi.org/10.1137/0221015openalex-snapshot
Locality in Distributed Graph Algorithms
inferredcites →https://doi.org/10.1137/06065310xopenalex-snapshot
A Primal-Dual Bicriteria Distributed Algorithm for Capacitated Vertex Cover
inferredcites →https://doi.org/10.1137/070683155openalex-snapshot
Graph Distances in the Data-Stream Model
inferredcites →https://doi.org/10.1137/1.9780898719772openalex-snapshot
Distributed Computing: A Locality-Sensitive Approach
inferredcites →https://doi.org/10.1137/1.9781611973099.91openalex-snapshot
Networks Cannot Compute Their Diameter in Sublinear Time
inferredcites →https://doi.org/10.1137/1.9781611973402.78openalex-snapshot
Better Approximation Algorithms for the Graph Diameter
inferredcites →https://doi.org/10.1137/1.9781611973730.82openalex-snapshot
Parameterized Streaming: Maximal Matching and Vertex Cover
inferredcites →https://doi.org/10.1137/1.9781611973730.84openalex-snapshot
Streaming Lower Bounds for Approximating MAX-CUT
inferredcites →https://doi.org/10.1137/1.9781611974331.ch27openalex-snapshot
New Bounds for Approximating Extremal Distances in Undirected Graphs
inferredcites →https://doi.org/10.1137/1.9781611974782.140openalex-snapshot
A (2 + ∊)-Approximation for Maximum Weight Matching in the Semi-Streaming Model
inferredcites →https://doi.org/10.1137/1.9781611975482.49openalex-snapshot
Optimal Distributed Coloring Algorithms for Planar Graphs in the LOCAL model
inferredcites →https://doi.org/10.1137/11085178xopenalex-snapshot
Distributed Verification and Hardness of Distributed Approximation
inferredcites →https://doi.org/10.1137/12088848xopenalex-snapshot
Distributed $(\Delta+1)$-Coloring in Linear (in $\Delta$) Time
inferredcites →https://doi.org/10.1137/s0097539700369740openalex-snapshot
A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction
inferredcites →https://doi.org/10.1137/s0097539704441058openalex-snapshot
An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
inferredcites →https://doi.org/10.1137/s0895480100373121openalex-snapshot
On the Distributed Complexity of Computing Maximal Matchings
inferredcites →https://doi.org/10.1137/s0895480100376794openalex-snapshot
On the Hardness of 4-Coloring a 3-Colorable Graph
inferredcites →https://doi.org/10.1145/1011767.1011791openalex-snapshot
Efficient algorithms for constructing (1+,ε, β)-spanners in the distributed and streaming models
inferredcites →https://doi.org/10.1145/1435375.1435381openalex-snapshot
Distributed weighted vertex cover via maximal matchings
inferredcites →https://doi.org/10.1145/1582716.1582746openalex-snapshot
Distributed and parallel algorithms for weighted vertex cover and other covering problems
inferredcites →https://doi.org/10.1145/1810479.1810533openalex-snapshot
Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks
inferredcites →https://doi.org/10.1145/1921659.1921666openalex-snapshot
Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners
inferredcites →https://doi.org/10.1145/1993806.1993853openalex-snapshot
A tight unconditional lower bound on distributed randomwalk computation
inferredcites →https://doi.org/10.1145/2027216.2027221openalex-snapshot
Deterministic Distributed Vertex Coloring in Polylogarithmic Time
inferredcites →https://doi.org/10.1145/2332432.2332504openalex-snapshot
Optimal distributed all pairs shortest paths and applications
inferredcites →https://doi.org/10.1145/2484239.2484262openalex-snapshot
Efficient distributed source detection with limited bandwidth
inferredcites →https://doi.org/10.1145/2488608.2488673openalex-snapshot
Fast approximation algorithms for the diameter and radius of sparse graphs
inferredcites →https://doi.org/10.1145/2591796.2591850openalex-snapshot
Distributed approximation algorithms for weighted shortest paths
inferredcites →https://doi.org/10.1145/2611462.2611465openalex-snapshot
Distributed algorithms for the Lovász local lemma and graph coloring
inferredcites →https://doi.org/10.1145/2611462.2611493openalex-snapshot
On the power of the congested clique model
inferredcites →https://doi.org/10.1145/2767386.2767398openalex-snapshot
Fast Partial Distance Estimation and Applications
inferredcites →https://doi.org/10.1145/2897518.2897533openalex-snapshot
Distributed (∆+1)-coloring in sublogarithmic rounds
inferredcites →https://doi.org/10.1145/2897518.2897638openalex-snapshot
A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
inferredcites →https://doi.org/10.1145/2903137openalex-snapshot
The Locality of Distributed Symmetry Breaking
inferredcites →https://doi.org/10.1145/2979675openalex-snapshot
Deterministic (Δ + 1)-Coloring in Sublinear (in Δ) Time in Static, Dynamic, and Faulty Networks
inferredcites →https://doi.org/10.1145/3055399.3055452openalex-snapshot
Distributed exact shortest paths in sublinear time
inferredcites →https://doi.org/10.1145/3087801.3087806openalex-snapshot
Distributed Approximation of Maximum Independent Set and Maximum Matching
inferredcites →https://doi.org/10.1145/3212734.3212740openalex-snapshot
Distributed Coloring in Sparse Graphs with Fewer Colors
inferredcites →https://doi.org/10.1145/3212734.3212773openalex-snapshot
A Deterministic Distributed Algorithm for Exact Weighted All-Pairs Shortest Paths in Õ(n 3/2 ) Rounds
inferredcites →https://doi.org/10.1145/3274668openalex-snapshot
A (2+ϵ)-Approximation for Maximum Weight Matching in the Semi-streaming Model
inferredcites →https://doi.org/10.1145/3293611.3331597openalex-snapshot
Hardness of Distributed Optimization
inferredcites →https://doi.org/10.1145/3313276.3316326openalex-snapshot
Distributed exact weighted all-pairs shortest paths in near-linear time
inferredcites →https://doi.org/10.1145/3313276.3316358openalex-snapshot
Planar diameter via metric compression
inferredcites →https://doi.org/10.1145/800135.804414openalex-snapshot
Some complexity questions related to distributive computing(Preliminary Report)
inferredcites →https://doi.org/10.1561/106.00000003openalex-snapshot
The Graph Structure in the Web − Analyzed on Different Aggregation Levels
inferredcites →https://doi.org/10.1561/9781933019604openalex-snapshot
Data Streams: Algorithms and Applications
inferredcites →https://doi.org/10.4230/lipics.disc.2017.10openalex-snapshot
Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model
inferredcites →https://doi.org/10.48550/arxiv.1704.06297openalex-snapshot
A Time Hierarchy Theorem for the LOCAL Model
inferredcites →https://doi.org/10.5555/2627817.2627938openalex-snapshot
Better bounds for matchings in the streaming model
inferredcites →https://doi.org/10.5555/2884435.2884462openalex-snapshot
New bounds for approximating extremal distances in undirected graphs
inferredcites →https://doi.org/10.5555/2884435.2884463openalex-snapshot
Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs
inferredcites →https://doi.org/10.5555/545381.545464openalex-snapshot
Reductions in streaming algorithms, with an application to counting triangles in graphs
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-3-031-60603-8_19openalex-snapshot
On Distributed Computation of the Minimum Triangle Edge Transversal
inferred← citeshttps://doi.org/10.1007/978-3-031-60603-8_5openalex-snapshot
k-Center Clustering in Distributed Models
inferred← citeshttps://doi.org/10.1145/3293611.3331581openalex-snapshot
Does Preprocessing Help under Congestion?
inferred← citeshttps://doi.org/10.1145/3313276.3316361openalex-snapshot
Polynomial pass lower bounds for graph streaming algorithms
inferred← citeshttps://doi.org/10.1145/3406325.3451081openalex-snapshot
Universally-optimal distributed algorithms for known topologies
inferred← citeshttps://doi.org/10.1145/3519935.3520016openalex-snapshot
Deterministic graph coloring in the streaming model
inferred← citeshttps://doi.org/10.1145/3623800.3623808openalex-snapshot
Recent Advances in Multi-Pass Graph Streaming Lower Bounds
inferred← citeshttps://doi.org/10.1145/3732772.3733506openalex-snapshot
Message Optimality and Message-Time Trade-offs for APSP and Beyond
inferred← citeshttps://doi.org/10.4230/lipics.opodis.2020.30openalex-snapshot
Distributed Distance Approximation
inferred← citeshttps://doi.org/10.46298/theoretics.23.9openalex-snapshot
Brooks' Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for $\Delta$-Coloring
inferred← citeshttps://doi.org/10.48550/arxiv.1905.03012openalex-snapshot
Brief Announcement: Does Preprocessing Help under Congestion?
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.