On the public citation graph

Functional oracle queries as a measure of parallel time

https://doi.org/10.1007/bfb0020817
0 signed · 27 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.1007/978-3-642-75357-2openalex-snapshot
Structural Complexity II
inferredcites →https://doi.org/10.1007/978-3-642-79235-9openalex-snapshot
Structural Complexity I
inferredcites →https://doi.org/10.1007/bf01683260openalex-snapshot
Relativization of questions about log space computability
inferredcites →https://doi.org/10.1007/bf01692056openalex-snapshot
RelativizedNC
inferredcites →https://doi.org/10.1007/bf02090764openalex-snapshot
Classes of bounded nondeterminism
inferredcites →https://doi.org/10.1016/0022-0000(81)90038-6openalex-snapshot
On uniform circuit complexity
inferredcites →https://doi.org/10.1016/0022-0000(88)90030-xopenalex-snapshot
Parallel computation with threshold functions
inferredcites →https://doi.org/10.1016/s0019-9958(85)80041-3openalex-snapshot
A taxonomy of problems with fast parallel algorithms
inferredcites →https://doi.org/10.1109/sct.1988.5271openalex-snapshot
Two applications of complementation via inductive counting
inferredcites →https://doi.org/10.1109/sct.1989.41818openalex-snapshot
Decomposing NC and AC
inferredcites →https://doi.org/10.1109/sct.1990.113964openalex-snapshot
A very hard log space counting class
inferredcites →https://doi.org/10.1137/0206054openalex-snapshot
On Relating Time and Space to Size and Depth
inferredcites →https://doi.org/10.1137/0218038openalex-snapshot
Two Applications of Inductive Counting for Complementation Problems
inferredcites →https://doi.org/10.1137/0219024openalex-snapshot
On the Decomposability of $NC$ and $AC$
inferredcites →https://doi.org/10.1145/12130.12138openalex-snapshot
The complexity of optimization problems

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1007/3-540-57785-8_151openalex-snapshot
NCk(NP)=AC k−1(NP)
inferred← citeshttps://doi.org/10.1007/978-3-662-22110-5_2openalex-snapshot
Complete Sets and Structure in Subrecursive Classes
inferred← citeshttps://doi.org/10.1016/0304-3975(93)90252-oopenalex-snapshot
A very hard log-space counting class
inferred← citeshttps://doi.org/10.1016/j.ic.2015.04.006openalex-snapshot
Computation by interaction for space-bounded functional programming
inferred← citeshttps://doi.org/10.1017/9781316716816.003openalex-snapshot
Complete Sets and Structure in Subrecursive Classes
inferred← citeshttps://doi.org/10.1109/ccc.1996.507666openalex-snapshot
Collapsing oracle-tape hierarchies
inferred← citeshttps://doi.org/10.1109/sct.1990.113964openalex-snapshot
A very hard log space counting class
inferred← citeshttps://doi.org/10.1109/sct.1991.160267openalex-snapshot
Adaptive logspace and depth-bounded reducibilities
inferred← citeshttps://doi.org/10.1109/sct.1993.336519openalex-snapshot
Computing functions with parallel queries to NP
inferred← citeshttps://doi.org/10.1145/201019.201031openalex-snapshot
NP trees and Carnap's modal logic
inferred← citeshttps://doi.org/10.4230/lipics.stacs.2017.35openalex-snapshot
Circuit Evaluation for Finite Semirings
inferred← citeshttps://doi.org/10.48550/arxiv.1602.04560openalex-snapshot
Circuit Evaluation for Finite Semirings
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.