On the public citation graph

A relationship between difference hierarchies and relativized polynomial hierarchies

https://doi.org/10.1007/bf01371729
0 signed · 74 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.1996.0001openalex-snapshot
PP Is Closed under Truth-Table Reductions
inferredcites →https://doi.org/10.1007/3-540-16079-5openalex-snapshot
Complexity and Structure
inferredcites →https://doi.org/10.1007/3-540-16486-3openalex-snapshot
Structure in Complexity Theory
inferredcites →https://doi.org/10.1007/3-540-16486-3_93openalex-snapshot
The boolean hierarchy: Hardware over NP
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/bf00289117openalex-snapshot
The complexity of combinatorial problems with succinct input representation
inferredcites →https://doi.org/10.1007/bf01202284openalex-snapshot
On the power of deterministic reductions to C=P
inferredcites →https://doi.org/10.1007/bf01303054openalex-snapshot
On computing Boolean connectives of characteristic functions
inferredcites →https://doi.org/10.1007/bfb0028832openalex-snapshot
On the boolean closure of NP
inferredcites →https://doi.org/10.1016/0304-3975(75)90016-xopenalex-snapshot
A comparison of polynomial time reducibilities
inferredcites →https://doi.org/10.1016/0304-3975(91)90160-4openalex-snapshot
Bounded queries to SAT and the Boolean hierarchy
inferredcites →https://doi.org/10.1016/0890-5401(88)90044-2openalex-snapshot
Polynomial terse sets
inferredcites →https://doi.org/10.1016/s0890-5401(03)00091-9openalex-snapshot
Some connections between bounded query classes and non-uniform complexity
inferredcites →https://doi.org/10.1051/ita/1987210404191openalex-snapshot
The difference and truth-table hierarchies for NP
inferredcites →https://doi.org/10.1109/sct.1988.5286openalex-snapshot
Bounded query computations
inferredcites →https://doi.org/10.1109/sct.1990.113963openalex-snapshot
A survey on counting classes
inferredcites →https://doi.org/10.1109/sct.1990.113965openalex-snapshot
The Boolean hierarchy and the polynomial hierarchy: a closer connection
inferredcites →https://doi.org/10.1109/sct.1991.160239openalex-snapshot
PP is closed under truth-table reductions
inferredcites →https://doi.org/10.1137/0215053openalex-snapshot
Sparse Sets, Lowness and Highness
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/0219058openalex-snapshot
Bounded Query Classes
inferredcites →https://doi.org/10.1137/s0097539790178069openalex-snapshot
The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
inferredcites →https://doi.org/10.1145/103418.103426openalex-snapshot
PP is closed under intersection
inferredcites →https://doi.org/10.1145/116825.116858openalex-snapshot
Complexity classes defined by counting quantifiers
inferredcites →https://doi.org/10.1145/147508.147546openalex-snapshot
Lower bounds for the low hierarchy

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.1006/inco.2000.2918openalex-snapshot
Commutative Queries
inferred← citeshttps://doi.org/10.1006/jcss.1995.1036openalex-snapshot
The Power of the Middle Bit of a #P Function
inferred← citeshttps://doi.org/10.1006/jcss.1999.1647openalex-snapshot
Two Queries
inferred← citeshttps://doi.org/10.1007/3-540-28520-2_5openalex-snapshot
Hierarchies Based on NP
inferred← citeshttps://doi.org/10.1007/3-540-28520-2_8openalex-snapshot
Other Public-Key Cryptosystems and Protocols
inferred← citeshttps://doi.org/10.1007/3-540-36494-3_48openalex-snapshot
One Bit of Advice
inferred← citeshttps://doi.org/10.1007/3-540-48321-7_9openalex-snapshot
Restrictive acceptance suffices for equivalence problems
inferred← citeshttps://doi.org/10.1007/3-540-49116-3_25openalex-snapshot
Extending Downward Collapse from 1-versus-2 Queries to j-versus-j + 1 Queries
inferred← citeshttps://doi.org/10.1007/3-540-68535-9_18openalex-snapshot
On Boolean Lowness and Boolean Highness
inferred← citeshttps://doi.org/10.1007/978-3-540-77120-3_14openalex-snapshot
The 1-Versus-2 Queries Problem Revisited
inferred← citeshttps://doi.org/10.1007/978-3-662-44465-8_51openalex-snapshot
The Two Queries Assumption and Arthur-Merlin Classes
inferred← citeshttps://doi.org/10.1007/bf01202284openalex-snapshot
On the power of deterministic reductions to C=P
inferred← citeshttps://doi.org/10.1007/bf01578841openalex-snapshot
Generalized theorems on relationships among reducibility notions to certain complexity classes
inferred← citeshttps://doi.org/10.1007/bfb0023469openalex-snapshot
A downward translation in the polynomial hierarchy
inferred← citeshttps://doi.org/10.1007/bfb0030862openalex-snapshot
Intersection suffices for Boolean hierarchy equivalence
inferred← citeshttps://doi.org/10.1007/bfb0036186openalex-snapshot
Query order in the polynomial hierarchy
inferred← citeshttps://doi.org/10.1007/s00224-004-1209-8openalex-snapshot
Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem
inferred← citeshttps://doi.org/10.1007/s00224-008-9126-xopenalex-snapshot
The 1-Versus-2 Queries Problem Revisited
inferred← citeshttps://doi.org/10.1016/j.jcss.2007.06.017openalex-snapshot
Proving SAT does not have small circuits with an application to the two queries problem
inferred← citeshttps://doi.org/10.1016/s0020-0190(03)00229-1openalex-snapshot
Exact complexity of Exact-Four-Colorability
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/s0304-3975(00)00146-8openalex-snapshot
On boolean lowness and boolean highness
inferred← citeshttps://doi.org/10.1051/ita/1996300200911openalex-snapshot
Bounded queries to arbitrary sets
inferred← citeshttps://doi.org/10.1051/ita:1999100openalex-snapshot
Immunity and Simplicity for Exact Counting and Other Counting Classes
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/ccc.2001.933876openalex-snapshot
Bounded query functions with limited output bits
inferred← citeshttps://doi.org/10.1109/ccc.2003.1214433openalex-snapshot
Proving SAT does not have small circuits with an application to the two queries problem
inferred← citeshttps://doi.org/10.1109/ccc.2007.7openalex-snapshot
Bounded Queries and the NP Machine Hypothesis
inferred← citeshttps://doi.org/10.1109/ccc.2008.32openalex-snapshot
Amplifying ZPP^SAT[1] and the Two Queries Problem
inferred← citeshttps://doi.org/10.1109/icci.1993.315404openalex-snapshot
Selectivity
inferred← citeshttps://doi.org/10.1109/ictta.2004.1307935openalex-snapshot
Complexity of the exact domatic number problem and of the exact conveyor flow shop problem
inferred← citeshttps://doi.org/10.1109/istcs.1997.595168openalex-snapshot
Commutative queries
inferred← citeshttps://doi.org/10.1109/sct.1991.160245openalex-snapshot
Bounded queries in recursion theory: a survey
inferred← citeshttps://doi.org/10.1112/s146115700000022xopenalex-snapshot
Restrictive Acceptance Suffices for Equivalence Problems
inferred← citeshttps://doi.org/10.1137/20m1383471openalex-snapshot
When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction Problems
inferred← citeshttps://doi.org/10.1137/s0097539701391002openalex-snapshot
Extending Downward Collapse from 1-versus-2 Queries to m -versus- m + 1 Queries
inferred← citeshttps://doi.org/10.1137/s0097539794261970openalex-snapshot
Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets
inferred← citeshttps://doi.org/10.1137/s0097539796297632openalex-snapshot
Query Order
inferred← citeshttps://doi.org/10.1137/s0097539796306474openalex-snapshot
A Downward Collapse within the Polynomial Hierarchy
inferred← citeshttps://doi.org/10.1145/219817.219822openalex-snapshot
Worlds to die for
inferred← citeshttps://doi.org/10.1145/261342.261344openalex-snapshot
Raising NP lower bounds to parallel NP lower bounds
inferred← citeshttps://doi.org/10.48550/arxiv.1806.03501openalex-snapshot
An Overview Of Some Semantic And Syntactic Complexity Classes
inferred← citeshttps://doi.org/10.48550/arxiv.cs/0106037openalex-snapshot
Using the No-Search Easy-Hard Technique for Downward Collapse
inferred← citeshttps://doi.org/10.48550/arxiv.cs/9808002openalex-snapshot
Downward Collapse from a Weaker Hypothesis
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.