On the public citation graph

Hardness results for dynamic problems by extensions of Fredman and Saks' chronogram method

https://doi.org/10.1007/bfb0055041
0 signed · 52 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.
Claim with ORCID
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.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1006/jagm.1994.1040openalex-snapshot
Dynamic Point Location in General Subdivisions
inferredcites →https://doi.org/10.1006/jagm.1996.0044openalex-snapshot
On-line Planar Graph Embedding
inferredcites →https://doi.org/10.1007/3-540-51542-9_5openalex-snapshot
Optimal algorithms for List Indexing and Subset Rank
inferredcites →https://doi.org/10.1007/3-540-57273-2_57openalex-snapshot
Fully dynamic planarity testing in planar embedded graphs
inferredcites →https://doi.org/10.1007/3-540-60220-8_54openalex-snapshot
Dynamic algorithms for the Dyck languages
inferredcites →https://doi.org/10.1007/3-540-60313-1_144openalex-snapshot
Fully Dynamic Transitive Closure in plane dags with one source and one sink
inferredcites →https://doi.org/10.1007/3-540-61422-2_132openalex-snapshot
Lower bounds for dynamic transitive closure, planar point location, and parentheses matching
inferredcites →https://doi.org/10.1007/978-1-4612-1098-6openalex-snapshot
Computational Geometry
inferredcites →https://doi.org/10.1007/bf01840401openalex-snapshot
Dynamic maintenance of planar digraphs, with applications
inferredcites →https://doi.org/10.1007/bf02126797openalex-snapshot
A lower bound for finding predecessors in Yao's cell probe model
inferredcites →https://doi.org/10.1007/bfb0028550openalex-snapshot
Searching Constant Width Mazes Captures the AC0 Hierarchy
inferredcites →https://doi.org/10.1007/bfb0055041openalex-snapshot
Hardness results for dynamic problems by extensions of Fredman and Saks' chronogram method
inferredcites →https://doi.org/10.1007/pl00009228openalex-snapshot
Lower Bounds for Fully Dynamic Connectivity Problems in Graphs
inferredcites →https://doi.org/10.1016/0020-0190(87)90163-3openalex-snapshot
The complexity of symmetric functions in bounded-depth circuits
inferredcites →https://doi.org/10.1016/0020-0190(87)90216-xopenalex-snapshot
Generalized lower bounds derived from Hastad's main lemma
inferredcites →https://doi.org/10.1016/0304-3975(94)90159-7openalex-snapshot
Complexity models for incremental computation
inferredcites →https://doi.org/10.1016/s0020-0190(97)00056-2openalex-snapshot
Dynamic connectivity in digital images
inferredcites →https://doi.org/10.1109/sfcs.1991.185428openalex-snapshot
Lower bounds for data structure problems on RAMs
inferredcites →https://doi.org/10.1137/0207012openalex-snapshot
Observations on the Complexity of Generating Quasi-Gray Codes
inferredcites →https://doi.org/10.1137/0214022openalex-snapshot
On the Complexity of Maintaining Partial Sums
inferredcites →https://doi.org/10.1137/0218056openalex-snapshot
Fully Dynamic Point Location in a Monotone Subdivision
inferredcites →https://doi.org/10.1145/12130.12132openalex-snapshot
Almost optimal lower bounds for small depth circuits
inferredcites →https://doi.org/10.1145/195058.195415openalex-snapshot
Lower bounds for union-split-find related problems on random access machines
inferredcites →https://doi.org/10.1145/225058.225093openalex-snapshot
On data structures and asymmetric communication complexity
inferredcites →https://doi.org/10.1145/322261.322274openalex-snapshot
Should Tables Be Sorted?
inferredcites →https://doi.org/10.1145/322290.322305openalex-snapshot
The Complexity of Maintaining an Array and Computing Its Partial Sums
inferredcites →https://doi.org/10.1145/73007.73040openalex-snapshot
The cell probe complexity of dynamic data structures
inferredcites →https://doi.org/10.17169/refubium-21657openalex-snapshot
Dynamic point location in general subdivisions
inferredcites →https://doi.org/10.2307/3161201openalex-snapshot
Doctoral Dissertation
inferredcites →https://doi.org/10.7146/brics.v2i1.19503openalex-snapshot
Dynamic Algorithms for the Dyck Languages
inferredcites →https://doi.org/10.7146/brics.v4i32.18958openalex-snapshot
Hardness Results for Dynamic Problems by Extensions of Fredman and Saks’ Chronogram Method

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-540-70575-8_7openalex-snapshot
Cell-Probe Proofs and Nondeterministic Cell-Probe Complexity
inferred← citeshttps://doi.org/10.1007/978-3-662-43948-7_86openalex-snapshot
Certificates in Data Structures
inferred← citeshttps://doi.org/10.1007/s004530010077openalex-snapshot
A Generalization of a Lower Bound Technique due to Fredman and Saks
inferred← citeshttps://doi.org/10.1016/j.ic.2004.04.006openalex-snapshot
Dynamic nested brackets
inferred← citeshttps://doi.org/10.1109/sfcs.1998.743504openalex-snapshot
Marked ancestor problems
inferred← citeshttps://doi.org/10.1137/s0097539701391592openalex-snapshot
New Lower Bound Techniques for Dynamic Partial Sums and Related Problems
inferred← citeshttps://doi.org/10.1145/1867719.1867720openalex-snapshot
Cell-Probe Proofs
inferred← citeshttps://doi.org/10.1145/335305.335357openalex-snapshot
Are bitvectors optimal?
inferred← citeshttps://doi.org/10.4230/lipics.icalp.2021.116openalex-snapshot
Dynamic Membership for Regular Languages
inferred← citeshttps://doi.org/10.48550/arxiv.cs/0302009openalex-snapshot
Data Structure for a Time-Based Bandwidth Reservations Problem
inferred← citeshttps://doi.org/10.48550/arxiv.cs/0308041openalex-snapshot
Static Data Structure for Discrete Advance Bandwidth Reservations on the Internet
inferred← citeshttps://doi.org/10.7146/brics.v4i32.18958openalex-snapshot
Hardness Results for Dynamic Problems by Extensions of Fredman and Saks’ Chronogram Method
inferred← citeshttps://doi.org/10.7146/brics.v4i33.18959openalex-snapshot
A Note on Frame Distributions
inferred← citeshttps://doi.org/10.7146/brics.v4i34.18960openalex-snapshot
Presheaf Models for the pi-Calculus
inferred← citeshttps://doi.org/10.7146/brics.v4i35.18961openalex-snapshot
A Theory of Recursive Domains with Applications to Concurrency
inferred← citeshttps://doi.org/10.7146/brics.v4i36.18962openalex-snapshot
Relational Semantics of Non-Deterministic Dataflow
inferred← citeshttps://doi.org/10.7146/brics.v4i38.18964openalex-snapshot
On the Distributed Complexity of Computing Maximal Matchings
inferred← citeshttps://doi.org/10.7146/brics.v4i39.18965openalex-snapshot
Names, Equations, Relations: Practical Ways to Reason about new
inferred← citeshttps://doi.org/10.7146/brics.v4i40.18966openalex-snapshot
Quantum Entanglement and Communication Complexity
inferred← citeshttps://doi.org/10.7146/brics.v5i7.19279openalex-snapshot
Marked Ancestor Problems (Preliminary Version)
showing the first 20 of 21 · page through all 21
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.