On the public citation graph

Self-reducible sets of small density

https://doi.org/10.1007/bf02090392
0 signed · 31 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/3-540-16079-5openalex-snapshot
Complexity and Structure
inferredcites →https://doi.org/10.1007/978-3-642-79235-9openalex-snapshot
Structural Complexity I
inferredcites →https://doi.org/10.1007/bfb0035750openalex-snapshot
Lower bounds for the low hierarchy
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(83)90013-2openalex-snapshot
On self-reducibility and weak P-selectivity
inferredcites →https://doi.org/10.1016/0022-0000(83)90027-2openalex-snapshot
A low and a high hierarchy within NP
inferredcites →https://doi.org/10.1108/ir.1999.04926fae.001openalex-snapshot
Lecture Notes in Computer Science 1205
inferredcites →https://doi.org/10.1109/sct.1988.5282openalex-snapshot
On truth-table reducibility to SAT and the difference hierarchy over NP
inferredcites →https://doi.org/10.1109/sct.1988.5286openalex-snapshot
Bounded query computations
inferredcites →https://doi.org/10.1137/0204037openalex-snapshot
Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
inferredcites →https://doi.org/10.1137/0208034openalex-snapshot
A Note on Sparse Complete Sets
inferredcites →https://doi.org/10.1137/0214003openalex-snapshot
On Circuit-Size Complexity and the Low Hierarchy in NP
inferredcites →https://doi.org/10.1145/147508.147546openalex-snapshot
Lower bounds for the low hierarchy
inferredcites →https://doi.org/10.1145/5925.5937openalex-snapshot
The polynomial-time hierarchy and sparse oracles

What points at this work

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

inferred← citeshttps://doi.org/10.1007/11672142_37openalex-snapshot
Sparse Selfreducible Sets and Polynomial Size Circuit Lower Bounds
inferred← citeshttps://doi.org/10.1007/3-540-55210-3_192openalex-snapshot
Characterizations of some complexity classes between Θ2p and Δ2p
inferred← citeshttps://doi.org/10.1007/3-540-56279-6_78openalex-snapshot
Lowness and the complexity of sparse and tally descriptions
inferred← citeshttps://doi.org/10.1007/3-540-57182-5_15openalex-snapshot
Hausdorff reductions to sparse sets and to sets of high information content
inferred← citeshttps://doi.org/10.1007/3-540-57811-0_17openalex-snapshot
On self-reducible sets of low information content
inferred← citeshttps://doi.org/10.1007/3-540-60084-1_74openalex-snapshot
New collapse consequences of NP having small circuits
inferred← citeshttps://doi.org/10.1007/bf01185399openalex-snapshot
A refinement of the low and high hierarchies
inferred← citeshttps://doi.org/10.1007/bf01201814openalex-snapshot
Upper Bounds for the Complexity of Sparse and Tally Descriptions
inferred← citeshttps://doi.org/10.1007/bf01206639openalex-snapshot
Space-efficient recognition of sparse self-reducible languages
inferred← citeshttps://doi.org/10.1007/s00453-018-0439-0openalex-snapshot
Sparse Selfreducible Sets and Nonuniform Lower Bounds
inferred← citeshttps://doi.org/10.1016/0304-3975(93)90020-topenalex-snapshot
On sparse hard sets for counting classes
inferred← citeshttps://doi.org/10.1016/0304-3975(95)00073-9openalex-snapshot
Geometric sets of low information content
inferred← citeshttps://doi.org/10.1051/ita/1996300201011openalex-snapshot
Complexity classes between $\Theta _k^P$ and $\Delta _k^P$
inferred← citeshttps://doi.org/10.1109/sct.1991.160254openalex-snapshot
On one query, self-reducible sets
inferred← citeshttps://doi.org/10.1109/sct.1992.215396openalex-snapshot
How hard are sparse sets?
inferred← citeshttps://doi.org/10.1109/sct.1995.514865openalex-snapshot
Reductions of self-reducible sets to depth-1 weighted threshold circuit classes, and sparse sets
inferred← citeshttps://doi.org/10.1137/s0097539795296206openalex-snapshot
New Collapse Consequences of NP Having Small Circuits
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.