On the public citation graph

A downward translation in the polynomial hierarchy

https://doi.org/10.1007/bfb0023469
0 signed · 33 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/inco.1995.1119openalex-snapshot
Defying Upward and Downward Separation
inferredcites →https://doi.org/10.1007/3-540-51498-8_4openalex-snapshot
Generalized Boolean hierarchies and Boolean hierarchies over RP
inferredcites →https://doi.org/10.1007/bf01275486openalex-snapshot
BPP has subexponential time simulations unlessEXPTIME has publishable proofs
inferredcites →https://doi.org/10.1007/bf01371729openalex-snapshot
A relationship between difference hierarchies and relativized polynomial hierarchies
inferredcites →https://doi.org/10.1007/bf02090390openalex-snapshot
Limitations of the upward separation technique
inferredcites →https://doi.org/10.1007/bfb0028832openalex-snapshot
On the boolean closure of NP
inferredcites →https://doi.org/10.1007/s002360050109openalex-snapshot
Easy sets and hard certificate schemes
inferredcites →https://doi.org/10.1016/0020-0190(94)90123-6openalex-snapshot
Upward separation for FewP and related classes
inferredcites →https://doi.org/10.1016/0304-3975(90)90099-4openalex-snapshot
Downward translations of equality
inferredcites →https://doi.org/10.1016/s0019-9958(74)90473-2openalex-snapshot
Tally languages and complexity classes
inferredcites →https://doi.org/10.1016/s0019-9958(85)80004-8openalex-snapshot
Sparse sets in NP-P: EXPTIME versus NEXPTIME
inferredcites →https://doi.org/10.1051/ita/1987210404191openalex-snapshot
The difference and truth-table hierarchies for NP
inferredcites →https://doi.org/10.1137/0217078openalex-snapshot
The Boolean Hierarchy I: Structural Properties
inferredcites →https://doi.org/10.1137/0217080openalex-snapshot
The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
inferredcites →https://doi.org/10.1137/0218007openalex-snapshot
The Boolean Hierarchy II: Applications
inferredcites →https://doi.org/10.1137/0218027openalex-snapshot
Relativized Polynomial Time Hierarchies Having Exactly K Levels
inferredcites →https://doi.org/10.1137/s0097539790178069openalex-snapshot
The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
inferredcites →https://doi.org/10.1137/s0097539794261970openalex-snapshot
Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets
inferredcites →https://doi.org/10.1142/s0129054190000151openalex-snapshot
STRONG SEPARATIONS FOR THE BOOLEAN HIERARCHY OVER RP
inferredcites →https://doi.org/10.1145/219817.219822openalex-snapshot
Worlds to die for

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.2000.2884openalex-snapshot
Bounded Queries, Approximations, and the Boolean Hierarchy
inferred← citeshttps://doi.org/10.1007/3-540-62592-5_60openalex-snapshot
R1−tt SN (NP) distinguishes robust many-one and Turing completeness
inferred← citeshttps://doi.org/10.1007/3-540-68535-9_18openalex-snapshot
On Boolean Lowness and Boolean Highness
inferred← citeshttps://doi.org/10.1007/bfb0036186openalex-snapshot
Query order in the polynomial hierarchy
inferred← citeshttps://doi.org/10.1016/s0020-0190(98)00024-6openalex-snapshot
A note on parallel queries and the symmetric-difference hierarchy
inferred← citeshttps://doi.org/10.1016/s0168-0072(99)00008-1openalex-snapshot
Structure and definability in general bounded arithmetic theories
inferred← citeshttps://doi.org/10.1016/s0304-3975(00)00146-8openalex-snapshot
On boolean lowness and boolean highness
inferred← citeshttps://doi.org/10.1109/ccc.1998.694586openalex-snapshot
Two queries
inferred← citeshttps://doi.org/10.1109/ccc.1999.766273openalex-snapshot
Quantum bounded query complexity
inferred← citeshttps://doi.org/10.1109/istcs.1997.595168openalex-snapshot
Commutative queries
inferred← citeshttps://doi.org/10.48550/arxiv.cs/9910002openalex-snapshot
What's Up with Downward Collapse: Using the Easy-Hard Technique to Link Boolean and Polynomial Hierarchy Collapses
inferred← citeshttps://doi.org/10.48550/arxiv.cs/9910004openalex-snapshot
An Introduction to Query Order
inferred← citeshttps://doi.org/10.48550/arxiv.cs/9910008openalex-snapshot
Translating Equality Downwards
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.