On the public citation graph
Collapsing oracle hierarchies, census functions and logarithmically many queries
0 signed · 40 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.1007/3-540-16761-7_93openalex-snapshot
More complicated questions about maxima and minima, and some closures of NP
inferredcites →https://doi.org/10.1007/bf01683260openalex-snapshot
Relativization of questions about log space computability
inferredcites →https://doi.org/10.1007/bfb0009651openalex-snapshot
Two remarks on the power of counting
inferredcites →https://doi.org/10.1007/bfb0036487openalex-snapshot
Two remarks on the power of counting
inferredcites →https://doi.org/10.1016/0022-0000(82)90002-2openalex-snapshot
Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis
inferredcites →https://doi.org/10.1016/0022-0000(84)90066-7openalex-snapshot
Space-bounded hierarchies and probabilistic computations
inferredcites →https://doi.org/10.1016/0022-0000(87)90009-2openalex-snapshot
Σ2 SPACE(n) is closed under complement
inferredcites →https://doi.org/10.1016/0022-0000(89)90024-xopenalex-snapshot
PNP[(log )] and sparse turing-complete sets for NP
inferredcites →https://doi.org/10.1016/0022-0000(89)90025-1openalex-snapshot
The strong exponential hierarchy collapses
inferredcites →https://doi.org/10.1109/psct.1987.10319251openalex-snapshot
A Structural Theorem that Depends Quantitatively on the Complexity of SAT
inferredcites →https://doi.org/10.1109/psct.1987.10319252openalex-snapshot
P NP [log n] and Sparse Turing-Complete Sets for NP
inferredcites →https://doi.org/10.1109/sct.1988.5270openalex-snapshot
Nondeterministic space is closed under complementation
inferredcites →https://doi.org/10.1145/12130.12138openalex-snapshot
The complexity of optimization problems
inferredcites →https://doi.org/10.1145/28395.28408openalex-snapshot
The strong exponential hierarchy collapses
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1006/inco.1995.1015openalex-snapshot
Feasible Computability and Resource Bounded Topology
inferred← citeshttps://doi.org/10.1007/3-540-19488-6_122openalex-snapshot
New developments in structural complexity theory
inferred← citeshttps://doi.org/10.1007/3-540-56503-5_3openalex-snapshot
Alternation for two-way machines with sublogarithmic space
inferred← citeshttps://doi.org/10.1007/978-1-4612-4478-3_4openalex-snapshot
Juris Hartmanis: Fundamental Contributions to Isomorphism Problems
inferred← citeshttps://doi.org/10.1007/978-3-319-04657-0_26openalex-snapshot
Collapsing Exact Arithmetic Hierarchies
inferred← citeshttps://doi.org/10.1007/bf01271368openalex-snapshot
The alternation hierarchy for sublogarithmic space is infinite
inferred← citeshttps://doi.org/10.1007/bfb0015925openalex-snapshot
Complexity theory and formal languages
inferred← citeshttps://doi.org/10.1007/bfb0017131openalex-snapshot
Structure of complexity classes: Separations, collapses, and completeness
inferred← citeshttps://doi.org/10.1007/bfb0035838openalex-snapshot
Characterizing the polynomial Hierarchy by alternating auxiliary pushdown automata
inferred← citeshttps://doi.org/10.1007/bfb0052085openalex-snapshot
Closure under complementation of logspace complexity classes - A survey -
inferred← citeshttps://doi.org/10.1007/s00037-012-0047-3openalex-snapshot
On the power of unambiguity in log-space
inferred← citeshttps://doi.org/10.1016/0020-0190(94)00059-xopenalex-snapshot
Census techniques collapse space classes
inferred← citeshttps://doi.org/10.1016/0022-0000(89)90025-1openalex-snapshot
The strong exponential hierarchy collapses
inferred← citeshttps://doi.org/10.1016/0304-3975(90)90191-jopenalex-snapshot
New developments in structural complexity theory
inferred← citeshttps://doi.org/10.1016/0304-3975(91)90160-4openalex-snapshot
Bounded queries to SAT and the Boolean hierarchy
inferred← citeshttps://doi.org/10.1016/0890-5401(89)90012-6openalex-snapshot
The logarithmic alternation hierarchy collapses: AΣ2L = AΠ2L
inferred← citeshttps://doi.org/10.1016/j.artint.2022.103685openalex-snapshot
Inconsistency-tolerant query answering for existential rules
inferred← citeshttps://doi.org/10.1016/j.artint.2022.103772openalex-snapshot
Preference-based inconsistency-tolerant query answering under existential rules
inferred← citeshttps://doi.org/10.1051/ita/1993270403491openalex-snapshot
Sublogarithmic $\sum _2$-space is not closed under complement and other separation results
inferred← citeshttps://doi.org/10.1051/ita/1994280504651openalex-snapshot
A hierarchy that does not collapse : alternations in low level space
inferred← citeshttps://doi.org/10.1109/sct.1993.336519openalex-snapshot
Computing functions with parallel queries to NP
inferred← citeshttps://doi.org/10.1137/0218038openalex-snapshot
Two Applications of Inductive Counting for Complementation Problems
inferred← citeshttps://doi.org/10.1145/201019.201031openalex-snapshot
NP trees and Carnap's modal logic
inferred← citeshttps://doi.org/10.1145/507457.507465openalex-snapshot
SIGACT news complexity theory column 35
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.