On the public citation graph
Query complexity, or why is it difficult to separateNP A ∩coNP A fromP A by random oraclesA?
0 signed · 100 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.1016/0022-0000(88)90028-1openalex-snapshot
Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
inferredcites →https://doi.org/10.1016/0304-3975(81)90061-xopenalex-snapshot
Bounded query machines: On NP and PSPACE
inferredcites →https://doi.org/10.1016/0304-3975(81)90062-1openalex-snapshot
Bounded query machines: On NP() and NPQUERY()
inferredcites →https://doi.org/10.1109/psct.1987.10319267openalex-snapshot
One-Way Functions, Robustness, and the Non-Isomorphism of NP-Complete Sets
inferredcites →https://doi.org/10.1109/sfcs.1981.35openalex-snapshot
Parity, circuits, and the polynomial-time hierarchy
inferredcites →https://doi.org/10.1109/sfcs.1985.49openalex-snapshot
Separating the polynomial-time hierarchy by oracles
inferredcites →https://doi.org/10.1109/sfcs.1987.30openalex-snapshot
Generic oracles and oracle classes
inferredcites →https://doi.org/10.1137/0204018openalex-snapshot
Every Prime Has a Succinct Certificate
inferredcites →https://doi.org/10.1137/0204037openalex-snapshot
Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
inferredcites →https://doi.org/10.1137/0210008openalex-snapshot
Relative to a Random Oracle A , ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
inferredcites →https://doi.org/10.1137/0213030openalex-snapshot
Quantitative Relativizations of Complexity Classes
inferredcites →https://doi.org/10.1145/12130.12133openalex-snapshot
With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
inferredcites →https://doi.org/10.1145/12130.12137openalex-snapshot
Private coins versus public coins in interactive proof systems
inferredcites →https://doi.org/10.1145/22145.22178openalex-snapshot
The knowledge complexity of interactive proof-systems
inferredcites →https://doi.org/10.1145/22145.22192openalex-snapshot
Trading group theory for randomness
inferredcites →https://doi.org/10.1145/800061.808733openalex-snapshot
Borel sets and circuit complexity
inferredcites →https://doi.org/10.1145/800061.808742openalex-snapshot
On notions of information transfer in VLSI circuits
inferredcites →https://doi.org/10.1145/800070.802195openalex-snapshot
On the random oracle hypothesis
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1002/rsa.20598openalex-snapshot
Improved bounds for the randomized decision tree Complexity of recursive majority
inferred← citeshttps://doi.org/10.1002/rsa.3240060108openalex-snapshot
On the Monte carlo boolean decision tree complexity of read‐once formulae
inferred← citeshttps://doi.org/10.1006/inco.1997.2646openalex-snapshot
A Tight Relationship between Generic Oracles and Type-2 Complexity Theory
inferred← citeshttps://doi.org/10.1006/jcss.1995.1030openalex-snapshot
Complexity Classes and Sparse Oracles
inferred← citeshttps://doi.org/10.1006/jcss.1998.1575openalex-snapshot
The Relative Complexity of NP Search Problems
inferred← citeshttps://doi.org/10.1006/jcss.1999.1654openalex-snapshot
Arthur-Merlin games in Boolean decision trees
inferred← citeshttps://doi.org/10.1007/3-540-36494-3_19openalex-snapshot
On the Complexity of Finding a Local Maximum of Functions on Discrete Planar Subsets
inferred← citeshttps://doi.org/10.1007/3-540-52048-1_44openalex-snapshot
On the limitations of locally robust positive reductions
inferred← citeshttps://doi.org/10.1007/3-540-54967-6_70openalex-snapshot
On the structure and complexity of infinite sets with minimal perfect hash functions
inferred← citeshttps://doi.org/10.1007/3-540-56939-1_72openalex-snapshot
Fault-tolerance and complexity (Extended abstract)
inferred← citeshttps://doi.org/10.1007/978-3-030-59212-7_12openalex-snapshot
Adaptive Exact Learning in a Mixed-Up World: Dealing with Periodicity, Errors and Jumbled-Index Queries in String Reconstruction
inferred← citeshttps://doi.org/10.1007/978-3-031-20624-5_18openalex-snapshot
Exact Learning of Multitrees and Almost-Trees Using Path Queries
inferred← citeshttps://doi.org/10.1007/978-3-031-65665-1_11openalex-snapshot
On Complexity of Deterministic and Nondeterministic Decision Trees for Decision Tables with Many-Valued Decisions from Closed Classes
inferred← citeshttps://doi.org/10.1007/978-3-031-65665-1_12openalex-snapshot
Simulating Functioning of Decision Trees for Tasks on Decision Rule Systems
inferred← citeshttps://doi.org/10.1007/978-3-031-92744-7_29openalex-snapshot
Deterministic and Nondeterministic Decision Trees for Recognition of Properties of Decision Rule Systems
inferred← citeshttps://doi.org/10.1007/978-3-032-14118-7_4openalex-snapshot
Recognizing Properties of Decision Rule Systems Using Deterministic and Nondeterministic Decision Trees
inferred← citeshttps://doi.org/10.1007/978-3-032-14118-7_5openalex-snapshot
Efficient Modeling of Deterministic Decision Trees for Recognizing Realizable Decision Rules
inferred← citeshttps://doi.org/10.1007/978-3-032-14118-7_7openalex-snapshot
Closed Classes of Binary Complete Decision Tables with Many-Valued Decisions
inferred← citeshttps://doi.org/10.1007/978-3-319-90530-3_18openalex-snapshot
Quadratically Tight Relations for Randomized Query Complexity
inferred← citeshttps://doi.org/10.1007/978-3-540-73556-4_34openalex-snapshot
The Computational Complexity of Game Trees by Eigen-Distribution
inferred← citeshttps://doi.org/10.1007/978-3-642-19571-6_36openalex-snapshot
On Black-Box Separations among Injective One-Way Functions
inferred← citeshttps://doi.org/10.1007/978-3-642-22006-7_27openalex-snapshot
Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority
inferred← citeshttps://doi.org/10.1007/978-3-642-24508-4openalex-snapshot
Boolean Function Complexity: Advances and Frontiers
inferred← citeshttps://doi.org/10.1007/978-3-642-32009-5_41openalex-snapshot
The Curious Case of Non-Interactive Commitments – On the Power of Black-Box vs. Non-Black-Box Use of Primitives
inferred← citeshttps://doi.org/10.1007/978-981-99-8730-6_11openalex-snapshot
On the (Im)possibility of Time-Lock Puzzles in the Quantum Random Oracle Model
inferred← citeshttps://doi.org/10.1007/bf01374524openalex-snapshot
Structural properties for feasibly computable classes of type two
inferred← citeshttps://doi.org/10.1007/bf02679447openalex-snapshot
Helping by Unambiguous Computation and Probabilistic Computation
inferred← citeshttps://doi.org/10.1007/bfb0017131openalex-snapshot
Structure of complexity classes: Separations, collapses, and completeness
inferred← citeshttps://doi.org/10.1007/bfb0029975openalex-snapshot
On P versus NP∩co-NP for decision trees and read-once branching programs
inferred← citeshttps://doi.org/10.1007/s00037-001-8190-2openalex-snapshot
Two oracles that force a big crunch
inferred← citeshttps://doi.org/10.1007/s00224-019-09935-xopenalex-snapshot
Quadratically Tight Relations for Randomized Query Complexity
inferred← citeshttps://doi.org/10.1007/s13748-021-00234-6openalex-snapshot
Existence versus exploitation: the opacity of backdoors and backbones
inferred← citeshttps://doi.org/10.1016/0020-0190(91)90054-lopenalex-snapshot
On random oracle separations
inferred← citeshttps://doi.org/10.1016/0304-3975(92)90318-aopenalex-snapshot
Separating complexity classes with tally oracles
inferred← citeshttps://doi.org/10.1016/j.ipl.2005.08.003openalex-snapshot
On the P versus NP intersected with co-NP question in communication complexity
inferred← citeshttps://doi.org/10.1016/j.tcs.2020.11.013openalex-snapshot
Being a permutation is also orthogonal to one-wayness in quantum world: Impossibilities of quantum one-way permutations from one-wayness primitives
inferred← citeshttps://doi.org/10.1016/j.tcs.2023.114177openalex-snapshot
On (simple) decision tree rank
inferred← citeshttps://doi.org/10.1016/s0022-0000(05)80003-0openalex-snapshot
Exact lower time bounds for computing Boolean functions on CREW PRAMs
inferred← citeshttps://doi.org/10.1016/s0304-3975(01)00144-xopenalex-snapshot
Complexity measures and decision tree complexity: a survey
inferred← citeshttps://doi.org/10.1016/s0304-3975(03)00426-2openalex-snapshot
On the complexity of finding a local maximum of functions on discrete planar subsets
inferred← citeshttps://doi.org/10.1016/s0304-3975(98)00071-1openalex-snapshot
Randomized Boolean decision trees: Several remarks
inferred← citeshttps://doi.org/10.1017/cbo9781139814782openalex-snapshot
Analysis of Boolean Functions
inferred← citeshttps://doi.org/10.1017/s0963548310000465openalex-snapshot
The Dual BKR Inequality and Rudich's Conjecture
inferred← citeshttps://doi.org/10.1109/access.2025.3610956openalex-snapshot
Comparison of Complexity of Regular Versus Oblivious Decision Trees for Decision Tables With Many-Valued Decisions From Closed Classes
inferred← citeshttps://doi.org/10.1109/ccc.2000.856739openalex-snapshot
A dual version of Reimer's inequality and a proof of Rudich's conjecture
inferred← citeshttps://doi.org/10.1109/ccc.2000.856758openalex-snapshot
Characterization of non-deterministic quantum query and quantum communication complexity
inferred← citeshttps://doi.org/10.1109/ccc.2009.33openalex-snapshot
Multitask Efficiencies in the Decision Tree Model
inferred← citeshttps://doi.org/10.1109/lics.2000.855757openalex-snapshot
Resource-bounded continuity and sequentiality for type-two functionals
inferred← citeshttps://doi.org/10.1109/sct.1995.514729openalex-snapshot
Decision trees with AND, OR queries
inferred← citeshttps://doi.org/10.1109/sfcs.1991.185422openalex-snapshot
Search problems in the decision tree model
inferred← citeshttps://doi.org/10.1137/0221052openalex-snapshot
Determinism vs. Nondeterminism in Multiparty Communication Complexity
inferred← citeshttps://doi.org/10.1137/17m1124115openalex-snapshot
Separation Between Deterministic and Randomized Query Complexity
inferred← citeshttps://doi.org/10.1137/17m1161737openalex-snapshot
A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$
inferred← citeshttps://doi.org/10.1137/s0895480192233867openalex-snapshot
Search Problems in the Decision Tree Model
inferred← citeshttps://doi.org/10.1145/225058.225147openalex-snapshot
The relative complexity of NP search problems
inferred← citeshttps://doi.org/10.1145/2840728.2840734openalex-snapshot
The Complexity of DNF of Parities
inferred← citeshttps://doi.org/10.1145/2897518.2897524openalex-snapshot
Separations in query complexity based on pointer functions
inferred← citeshttps://doi.org/10.1145/3095799openalex-snapshot
An Average-Case Depth Hierarchy Theorem for Boolean Circuits
inferred← citeshttps://doi.org/10.1145/3106234openalex-snapshot
Separations in Query Complexity Based on Pointer Functions
inferred← citeshttps://doi.org/10.1145/3369937openalex-snapshot
Search versus Decision for Election Manipulation Problems
inferred← citeshttps://doi.org/10.1145/3564246.3585119openalex-snapshot
Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness
inferred← citeshttps://doi.org/10.1145/3564246.3585199openalex-snapshot
Randomized versus Deterministic Decision Tree Size
inferred← citeshttps://doi.org/10.1145/507382.507387openalex-snapshot
Resource-bounded continuity and sequentiality for type-two functionals
inferred← citeshttps://doi.org/10.1145/509907.509942openalex-snapshot
Reimer's inequality and tardos' conjecture
inferred← citeshttps://doi.org/10.1145/780542.780640openalex-snapshot
Two applications of information complexity
inferred← citeshttps://doi.org/10.3233/sat190035openalex-snapshot
Disjoint DNF Tautologies with Conflict Bound Two
inferred← citeshttps://doi.org/10.3390/axioms14110794openalex-snapshot
Efficient Modeling of Deterministic Decision Trees for Recognition of Realizable Decision Rules: Bounds on Weighted Depth
inferred← citeshttps://doi.org/10.3390/e25101411openalex-snapshot
On Complexity of Deterministic and Nondeterministic Decision Trees for Conventional Decision Tables from Closed Classes
inferred← citeshttps://doi.org/10.3390/e26060519openalex-snapshot
Comparative Analysis of Deterministic and Nondeterministic Decision Trees for Decision Tables from Closed Classes
inferred← citeshttps://doi.org/10.4230/lipics.ccc.2016.13openalex-snapshot
Degree and Sensitivity: Tails of Two Distributions
inferred← citeshttps://doi.org/10.4236/jilsa.2025.173013openalex-snapshot
Recognizing Properties of Decision Rule Systems Using Deterministic and Nondeterministic Decision Trees
inferred← citeshttps://doi.org/10.4236/jilsa.2025.174014openalex-snapshot
Closed Classes of Binary Complete Decision Tables with Many-Valued Decisions
inferred← citeshttps://doi.org/10.48550/arxiv.1309.7565openalex-snapshot
Improved bounds for the randomized decision tree complexity of recursive majority
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.