On the public citation graph
Relative to a Random Oracle A , ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
0 signed · 383 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/bf01683260openalex-snapshot
Relativization of questions about log space computability
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(80)90027-4openalex-snapshot
On counting problems and the polynomial-time hierarchy
inferredcites →https://doi.org/10.1016/b978-0-12-417750-5.50006-3openalex-snapshot
COMPUTATIONALLY COMPLEX AND PSEUDO-RANDOM ZERO-ONE VALUED FUNCTIONS††Portions of this work were carried out at Carngie-Mellon University, while the authors were in the Department of Computer Science. Portions of these results were reported in preliminary form in [1].
inferredcites →https://doi.org/10.1063/1.3034322openalex-snapshot
An Introduction to Probability Theory and Its Applications, Vol. 2
inferredcites →https://doi.org/10.1093/comjnl/12.1.28openalex-snapshot
Theory of Recursive Functions and Effective Computability
inferredcites →https://doi.org/10.1109/sfcs.1978.37openalex-snapshot
Two theorems on random polynomial time
inferredcites →https://doi.org/10.1109/sfcs.1980.40openalex-snapshot
Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis
inferredcites →https://doi.org/10.1109/tit.1976.1055638openalex-snapshot
New directions in cryptography
inferredcites →https://doi.org/10.1137/0204037openalex-snapshot
Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
inferredcites →https://doi.org/10.1137/0206023openalex-snapshot
On Isomorphisms and Density of $NP$ and Other Complete Sets
inferredcites →https://doi.org/10.1137/0206049openalex-snapshot
Computational Complexity of Probabilistic Turing Machines
inferredcites →https://doi.org/10.1145/321832.321840openalex-snapshot
On Almost Everywhere Complex Recursive Functions
inferredcites →https://doi.org/10.1145/321864.321877openalex-snapshot
On the Structure of Polynomial Time Reducibility
inferredcites →https://doi.org/10.1145/321892.321894openalex-snapshot
A Theory of Program Size Formally Identical to Information Theory
inferredcites →https://doi.org/10.1145/800133.804363openalex-snapshot
Relativized questions involving probabilistic algorithms
inferredcites →https://doi.org/10.1515/9781400882618-010openalex-snapshot
Computability by Probabilistic Machines
inferredcites →https://doi.org/10.2307/1527528openalex-snapshot
An Introduction to Probability Theory and Its Applications. Vol. II
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.3217/jucs-012-06-0746openalex-extracted
Randomized Algorithms and Complexity Theory
inferred← citeshttps://doi.org/10.1002/malq.19990450104openalex-snapshot
Towards the Actual Relationship Between NP and Exponential Time
inferred← citeshttps://doi.org/10.1002/malq.200310037openalex-snapshot
Generic separations and leaf languages
inferred← citeshttps://doi.org/10.1002/malq.200310116openalex-snapshot
Fast quantum algorithms for handling probabilistic and interval uncertainty
inferred← citeshttps://doi.org/10.1002/malq.202200068openalex-snapshot
Borel complexity and Ramsey largeness of sets of oracles separating complexity classes
inferred← citeshttps://doi.org/10.1006/inco.2001.3110openalex-snapshot
Almost-Everywhere Superiority for Quantum Polynomial Time
inferred← citeshttps://doi.org/10.1006/inco.2002.3149openalex-snapshot
Degrees of Dowd-Type Generic Oracles
inferred← citeshttps://doi.org/10.1006/jcss.1995.1032openalex-snapshot
Closure Properties and Witness Reduction
inferred← citeshttps://doi.org/10.1006/jcss.1996.0024openalex-snapshot
Structural Average Case Complexity
inferred← citeshttps://doi.org/10.1006/jcss.1996.0065openalex-snapshot
Relative to a Random Oracle, NP Is Not Small
inferred← citeshttps://doi.org/10.1006/jcss.1999.1651openalex-snapshot
Complexity Limitations on Quantum Computation
inferred← citeshttps://doi.org/10.1007/0-387-34799-2_2openalex-snapshot
Limits on the Provable Consequences of One-way Permutations
inferred← citeshttps://doi.org/10.1007/0-387-34799-2_41openalex-snapshot
On the Power of 1-way Functions
inferred← citeshttps://doi.org/10.1007/1-4020-8141-3_9openalex-snapshot
Resource Bounded Immunity and Simplicity
inferred← citeshttps://doi.org/10.1007/11821069_41openalex-snapshot
Dimension Characterizations of Complexity Classes
inferred← citeshttps://doi.org/10.1007/3-540-13883-8_72openalex-snapshot
A new characterization of BPP
inferred← citeshttps://doi.org/10.1007/3-540-16078-7_72openalex-snapshot
Speeding up random access machines by few processors
inferred← citeshttps://doi.org/10.1007/3-540-16486-3_105openalex-snapshot
Parallel computation with threshold functions
inferred← citeshttps://doi.org/10.1007/3-540-16486-3_109openalex-snapshot
Diagonalisation methods in a polynomial setting
inferred← citeshttps://doi.org/10.1007/3-540-16486-3_112openalex-snapshot
Probabilistic quantifiers, adversaries, and complexity classes : An overview
inferred← citeshttps://doi.org/10.1007/3-540-16486-3_87openalex-snapshot
Randomness, relativizations, and polynomial reducibilities
inferred← citeshttps://doi.org/10.1007/3-540-16486-3_93openalex-snapshot
The boolean hierarchy: Hardware over NP
inferred← citeshttps://doi.org/10.1007/3-540-16761-7_86openalex-snapshot
Lower bounds by recursion theoretic arguments
inferred← citeshttps://doi.org/10.1007/3-540-18170-9_166openalex-snapshot
Randomness, provability, and the separation of Monte Carlo Time and space
inferred← citeshttps://doi.org/10.1007/3-540-18625-5_67openalex-snapshot
Probabilistic quantifiers vs. distrustful adversaries
inferred← citeshttps://doi.org/10.1007/3-540-32743-6_8openalex-snapshot
Von der Turingmaschine zum Quantencomputer — ein Gang durch die Geschichte der Komplexitätstheorie
inferred← citeshttps://doi.org/10.1007/3-540-44612-5_29openalex-snapshot
On the Autoreducibility of Random Sequences
inferred← citeshttps://doi.org/10.1007/3-540-45022-x_77openalex-snapshot
The Global Power of Additional Queries to p-Random Oracles
inferred← citeshttps://doi.org/10.1007/3-540-45995-2_35openalex-snapshot
Category, Measure, Inductive Inference: A Triality Theorem and Its Applications
inferred← citeshttps://doi.org/10.1007/3-540-47555-9_21openalex-snapshot
A Simplified and Generalized Treatment of Luby-Rackoff Pseudorandom Permutation Generators
inferred← citeshttps://doi.org/10.1007/3-540-50241-6_25openalex-snapshot
Diagonalizing over deterministic polynomial time
inferred← citeshttps://doi.org/10.1007/3-540-51498-8_4openalex-snapshot
Generalized Boolean hierarchies and Boolean hierarchies over RP
inferred← citeshttps://doi.org/10.1007/3-540-52846-6_73openalex-snapshot
Structural complexity theory: Recent surprises
inferred← citeshttps://doi.org/10.1007/3-540-55210-3_193openalex-snapshot
On complexity classes and algorithmically random languages
inferred← citeshttps://doi.org/10.1007/3-540-55808-x_38openalex-snapshot
Almost every set in exponential time is P-bi-immune
inferred← citeshttps://doi.org/10.1007/3-540-56279-6_70openalex-snapshot
Relativizations of the P=? NP and other problems: Some developments in structural complexity theory
inferred← citeshttps://doi.org/10.1007/3-540-56939-1_75openalex-snapshot
On randomized versus deterministic computation
inferred← citeshttps://doi.org/10.1007/3-540-57568-5_255openalex-snapshot
Relativizing complexity classes with Random Oracles
inferred← citeshttps://doi.org/10.1007/3-540-58201-0_55openalex-snapshot
On the computational power of probabilistic and faulty neural networks
inferred← citeshttps://doi.org/10.1007/3-540-58201-0_74openalex-snapshot
On the cutting edge of relativization: The resource bounded injury method
inferred← citeshttps://doi.org/10.1007/3-540-58325-4_204openalex-snapshot
Separability and one-way functions
inferred← citeshttps://doi.org/10.1007/3-540-58338-6_69openalex-snapshot
Genericity and measure for exponential time
inferred← citeshttps://doi.org/10.1007/3-540-60246-1_114openalex-snapshot
On the computing paradigm and computational complexity
inferred← citeshttps://doi.org/10.1007/3-540-60246-1_124openalex-snapshot
Separations by random oracles and “Almost” classes for generalized reducibilities
inferred← citeshttps://doi.org/10.1007/3-540-60922-9_2openalex-snapshot
Compressibility and resource bounded measure
inferred← citeshttps://doi.org/10.1007/3-540-61440-0_141openalex-snapshot
On the power of randomized branching programs
inferred← citeshttps://doi.org/10.1007/3-540-61440-0_143openalex-snapshot
On type-2 probabilistic quantifiers
inferred← citeshttps://doi.org/10.1007/978-1-4471-0313-4_20openalex-snapshot
Quantum Computation Relative to Oracles
inferred← citeshttps://doi.org/10.1007/978-1-4471-0717-0_10openalex-snapshot
P-Immune Sets with Holes Lack Self-Reducibility Properties
inferred← citeshttps://doi.org/10.1007/978-1-4612-3466-1_17openalex-snapshot
Complexity-Theoretic Algebra: Vector Space Bases
inferred← citeshttps://doi.org/10.1007/978-1-4613-3394-4_14openalex-snapshot
Measure One Results in Computational Complexity Theory
inferred← citeshttps://doi.org/10.1007/978-3-030-80627-9_7openalex-snapshot
Algorithms and Complexity
inferred← citeshttps://doi.org/10.1007/978-3-031-84740-0_14openalex-snapshot
Circuit Complexity and Unambiguity
inferred← citeshttps://doi.org/10.1007/978-3-032-31348-5_22openalex-snapshot
Counting Random Oracles for the Polynomial-Time Hierarchy and Quantum Complexity Classes
inferred← citeshttps://doi.org/10.1007/978-3-319-32162-2_1openalex-snapshot
$$P\mathop{ =}\limits^{?}NP$$
inferred← citeshttps://doi.org/10.1007/978-3-319-43669-2_10openalex-snapshot
Complexity Barriers as Independence
inferred← citeshttps://doi.org/10.1007/978-3-540-31834-7_1openalex-snapshot
Algorithmic Randomness, Quantum Physics, and Incompleteness
inferred← citeshttps://doi.org/10.1007/978-3-540-69407-6_25openalex-snapshot
The Shrinking Property for NP and coNP
inferred← citeshttps://doi.org/10.1007/978-3-642-20573-6_67openalex-snapshot
Security and Trust Management in MANET
inferred← citeshttps://doi.org/10.1007/978-3-642-20712-9_13openalex-snapshot
Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas
inferred← citeshttps://doi.org/10.1007/978-3-642-25385-0_3openalex-snapshot
Random Oracles in a Quantum World
inferred← citeshttps://doi.org/10.1007/978-3-642-33272-2_7openalex-snapshot
Deterministic Random Oracles
inferred← citeshttps://doi.org/10.1007/978-3-642-42033-7_9openalex-snapshot
Reset Indifferentiability and Its Consequences
inferred← citeshttps://doi.org/10.1007/978-3-642-55220-5_33openalex-snapshot
Salvaging Indifferentiability in a Multi-stage Setting
inferred← citeshttps://doi.org/10.1007/978-3-642-60322-8_18openalex-snapshot
Probabilistic Algorithms, Probability Amplification, and the Recycling of Random Numbers
inferred← citeshttps://doi.org/10.1007/978-3-642-60322-8_23openalex-snapshot
P ≠ NP with probability 1
inferred← citeshttps://doi.org/10.1007/978-3-642-77735-6_2openalex-snapshot
Applications of Time-Bounded Kolmogorov Complexity in Complexity Theory
inferred← citeshttps://doi.org/10.1007/978-3-642-77735-6_3openalex-snapshot
On Sets with Small Information Content
inferred← citeshttps://doi.org/10.1007/978-3-662-05642-4_13openalex-snapshot
The Computer, Artificial Intelligence, and the Turing Test
inferred← citeshttps://doi.org/10.1007/978-3-662-07675-0_1openalex-snapshot
Complexity: A Language-Theoretic Point of View
inferred← citeshttps://doi.org/10.1007/978-3-7091-6597-3_8openalex-snapshot
Logical Depth and Physical Complexity
inferred← citeshttps://doi.org/10.1007/978-94-009-2411-6_2openalex-snapshot
Constructing Oracles by Lower Bound Techniques for Circuits
inferred← citeshttps://doi.org/10.1007/978-94-009-2411-6_3openalex-snapshot
Randomness, Tally Sets, and Complexity Classes
inferred← citeshttps://doi.org/10.1007/bf01184814openalex-snapshot
Strong Self-Reducibility Precludes Strong Immunity
inferred← citeshttps://doi.org/10.1007/bf01200120openalex-snapshot
Relativized isomorphisms of NP-complete sets
inferred← citeshttps://doi.org/10.1007/bf01202283openalex-snapshot
Structural analysis of the complexity of inverse functions
inferred← citeshttps://doi.org/10.1007/bf01206322openalex-snapshot
Weakly complete problems are not rare
inferred← citeshttps://doi.org/10.1007/bf01215346openalex-snapshot
The expressive power of voting polynomials
inferred← citeshttps://doi.org/10.1007/bf01270387openalex-snapshot
A lower bound for randomized algebraic decision trees
inferred← citeshttps://doi.org/10.1007/bf01275486openalex-snapshot
BPP has subexponential time simulations unlessEXPTIME has publishable proofs
inferred← citeshttps://doi.org/10.1007/bf01303057openalex-snapshot
On closure properties of bounded two-sided error complexity classes
inferred← citeshttps://doi.org/10.1007/bf01368782openalex-snapshot
Simultaneous strong separations of probabilistic and unambiguous complexity classes
inferred← citeshttps://doi.org/10.1007/bf01375474openalex-snapshot
Pseudorandom bits for constant depth circuits
inferred← citeshttps://doi.org/10.1007/bf01578842openalex-snapshot
An observation on probability versus randomness with applications to complexity classes
inferred← citeshttps://doi.org/10.1007/bf01699457openalex-snapshot
Bi-immune sets for complexity classes
inferred← citeshttps://doi.org/10.1007/bf01699469openalex-snapshot
Nonlevelable sets and immune sets in the accepting density hierarchy inNP
inferred← citeshttps://doi.org/10.1007/bf01704904openalex-snapshot
Complete sets and closeness to complexity classes
inferred← citeshttps://doi.org/10.1007/bf01874396openalex-snapshot
Randomized algorithms: An annotated bibliography
inferred← citeshttps://doi.org/10.1007/bf02088009openalex-snapshot
A second step toward the strong polynomial-time hierarchy
inferred← citeshttps://doi.org/10.1007/bf02090768openalex-snapshot
On the power of parity polynomial time
inferred← citeshttps://doi.org/10.1007/bf02090773openalex-snapshot
Characterizing polynomial complexity classes by reducibilities
inferred← citeshttps://doi.org/10.1007/bf02125350openalex-snapshot
Query complexity, or why is it difficult to separateNP A ∩coNP A fromP A by random oraclesA?
inferred← citeshttps://doi.org/10.1007/bfb0012790openalex-snapshot
On the power of probabilistic choice in synchronous parallel computations
inferred← citeshttps://doi.org/10.1007/bfb0016258openalex-snapshot
P-genericity and strong p-genericity
inferred← citeshttps://doi.org/10.1007/bfb0017127openalex-snapshot
Sparse sets, tally sets, and polynomial reducibilities
inferred← citeshttps://doi.org/10.1007/bfb0024022openalex-snapshot
Combined simplicity and immunity in relativized NP
inferred← citeshttps://doi.org/10.1007/bfb0028561openalex-snapshot
On the structure of valiant's complexity classes
inferred← citeshttps://doi.org/10.1007/bfb0028987openalex-snapshot
On the power of parity polynomial time
inferred← citeshttps://doi.org/10.1007/bfb0030859openalex-snapshot
Sets computable in polynomial time on average
inferred← citeshttps://doi.org/10.1007/bfb0036471openalex-snapshot
Controlled relativizations of P and NP
inferred← citeshttps://doi.org/10.1007/bfb0036938openalex-snapshot
Complexity classes of alternating machines with oracles
inferred← citeshttps://doi.org/10.1007/bfb0039599openalex-snapshot
Graph isomorphism is in the low hierarchy
inferred← citeshttps://doi.org/10.1007/bfb0039602openalex-snapshot
Probability one separation of the Boolean hierarchy
inferred← citeshttps://doi.org/10.1007/bfb0055796openalex-snapshot
Randomness vs. completeness: On the diagonalization strength of resource-bounded random sets
inferred← citeshttps://doi.org/10.1007/bfb0076220openalex-snapshot
Probabilistic machines, oracles, and quantifiers
inferred← citeshttps://doi.org/10.1007/bfb0083671openalex-snapshot
Computational complexity of languages counting random oracles
inferred← citeshttps://doi.org/10.1007/jhep04(2019)087openalex-snapshot
Time evolution of complexity: a critique of three methods
inferred← citeshttps://doi.org/10.1007/s00037-002-0173-4openalex-snapshot
Separability and one-way functions
inferred← citeshttps://doi.org/10.1007/s00153-005-0283-1openalex-snapshot
Bounded truth table does not reduce the one-query tautologies to a random oracle
inferred← citeshttps://doi.org/10.1007/s00153-008-0076-4openalex-snapshot
Does truth-table of linear norm reduce the one-query tautologies to a random oracle?
inferred← citeshttps://doi.org/10.1007/s00224-007-9024-7openalex-snapshot
Dimension Extractors and Optimal Decompression
inferred← citeshttps://doi.org/10.1007/s10955-008-9486-2openalex-snapshot
Using the Renormalization Group to Classify Boolean Functions
inferred← citeshttps://doi.org/10.1016/0020-0190(82)90139-9openalex-snapshot
Some observations on the probabilistic algorithms and NP-hard problems
inferred← citeshttps://doi.org/10.1016/0020-0190(83)90044-3openalex-snapshot
BPP and the polynomial hierarchy
inferred← citeshttps://doi.org/10.1016/0020-0190(87)90036-6openalex-snapshot
Random oracles separate PSPACE from the polynomial-time hierarchy
inferred← citeshttps://doi.org/10.1016/0020-0190(87)90232-8openalex-snapshot
Does co-NP have short interactive proofs?
inferred← citeshttps://doi.org/10.1016/0020-0190(90)90101-3openalex-snapshot
Lower bounds for constant-depth circuits in the presence of help bits
inferred← citeshttps://doi.org/10.1016/0020-0190(91)90035-gopenalex-snapshot
An oracle separating ΘP from PPPH
inferred← citeshttps://doi.org/10.1016/0020-0190(91)90054-lopenalex-snapshot
On random oracle separations
inferred← citeshttps://doi.org/10.1016/0020-0190(92)90225-kopenalex-snapshot
Circuit depth relative to a random oracle
inferred← citeshttps://doi.org/10.1016/0020-0190(93)90216-vopenalex-snapshot
The generic oracle hypothesis is false
inferred← citeshttps://doi.org/10.1016/0020-0190(94)00157-xopenalex-snapshot
On collapsing the polynomial-time hierarchy
inferred← citeshttps://doi.org/10.1016/0020-0190(94)00185-2openalex-snapshot
The relativized relationship between probabilistically checkable debate systems, IP and PSPACE
inferred← citeshttps://doi.org/10.1016/0020-0255(84)90036-7openalex-snapshot
“NP = P?” and restricted partitions
inferred← citeshttps://doi.org/10.1016/0022-0000(81)90034-9openalex-snapshot
A time-luck tradeoff in relativized cryptography
inferred← citeshttps://doi.org/10.1016/0022-0000(83)90013-2openalex-snapshot
On self-reducibility and weak P-selectivity
inferred← citeshttps://doi.org/10.1016/0022-0000(84)90066-7openalex-snapshot
Space-bounded hierarchies and probabilistic computations
inferred← citeshttps://doi.org/10.1016/0022-0000(85)90040-6openalex-snapshot
Relativized circuit complexity
inferred← citeshttps://doi.org/10.1016/0022-0000(88)90010-4openalex-snapshot
Graph isomorphism is in the low hierarchy
inferred← citeshttps://doi.org/10.1016/0022-0000(88)90028-1openalex-snapshot
Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
inferred← citeshttps://doi.org/10.1016/0022-0000(88)90030-xopenalex-snapshot
Parallel computation with threshold functions
inferred← citeshttps://doi.org/10.1016/0022-0000(88)90036-0openalex-snapshot
The topology of provability in complexity theory
inferred← citeshttps://doi.org/10.1016/0022-0000(88)90037-2openalex-snapshot
Probabilistic quantifiers and games
inferred← citeshttps://doi.org/10.1016/0022-0000(89)90020-2openalex-snapshot
Probabilistic complexity classes and lowness
inferred← citeshttps://doi.org/10.1016/0022-0000(89)90021-4openalex-snapshot
Some consequences of the existence of pseudorandom generators
inferred← citeshttps://doi.org/10.1016/0022-0000(89)90033-0openalex-snapshot
With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
inferred← citeshttps://doi.org/10.1016/0022-0000(91)90040-copenalex-snapshot
Relativized counting classes: Relations among thresholds, parity, and mods
inferred← citeshttps://doi.org/10.1016/0168-0072(86)90005-9openalex-snapshot
Approximation to measurable functions and its relation to probabilistic computation
inferred← citeshttps://doi.org/10.1016/0168-0072(89)90047-xopenalex-snapshot
Complexity-theoretic algebra II: Boolean algebras
inferred← citeshttps://doi.org/10.1016/0168-0072(95)00051-8openalex-snapshot
On the lattices of NP-subspaces of a polynomial time vector space over a finite field
inferred← citeshttps://doi.org/10.1016/0196-6774(82)90026-8openalex-snapshot
The NP-completeness column: An ongoing guide
inferred← citeshttps://doi.org/10.1016/0196-6774(84)90022-1openalex-snapshot
The NP-completeness column: An ongoing guide
inferred← citeshttps://doi.org/10.1016/0196-6774(86)90020-9openalex-snapshot
The NP-completeness column: An ongoing guide
inferred← citeshttps://doi.org/10.1016/0196-6774(88)90033-8openalex-snapshot
The NP-completeness column: An ongoing guide
inferred← citeshttps://doi.org/10.1016/0304-3975(83)90003-8openalex-snapshot
Oracle-dependent properties of the lattice of NP sets
inferred← citeshttps://doi.org/10.1016/0304-3975(84)90111-7openalex-snapshot
Computation times of NP sets of different densities
inferred← citeshttps://doi.org/10.1016/0304-3975(85)90017-9openalex-snapshot
Complete divisibility problems for slowly utilized oracles
inferred← citeshttps://doi.org/10.1016/0304-3975(85)90079-9openalex-snapshot
Simulating probabilistic by deterministic algebraic computation trees
inferred← citeshttps://doi.org/10.1016/0304-3975(85)90085-4openalex-snapshot
On some natural complete operators
inferred← citeshttps://doi.org/10.1016/0304-3975(86)90140-4openalex-snapshot
A classification of complexity core lattices
inferred← citeshttps://doi.org/10.1016/0304-3975(87)90053-3openalex-snapshot
Diagonalizations over polynomial time computable sets
inferred← citeshttps://doi.org/10.1016/0304-3975(87)90132-0openalex-snapshot
A comparison of polynomial time completeness notions
inferred← citeshttps://doi.org/10.1016/0304-3975(88)90022-9openalex-snapshot
Complexity classes without machines: On complete languages for UP
inferred← citeshttps://doi.org/10.1016/0304-3975(90)90177-jopenalex-snapshot
Bi-immunity results for cheatable sets
inferred← citeshttps://doi.org/10.1016/0304-3975(91)90314-ropenalex-snapshot
Polynomial-time reducibilities and “almost all” oracle sets
inferred← citeshttps://doi.org/10.1016/0304-3975(91)90320-2openalex-snapshot
An upward measure separation theorem
inferred← citeshttps://doi.org/10.1016/0304-3975(92)90125-yopenalex-snapshot
A uniform approach to define complexity classes
inferred← citeshttps://doi.org/10.1016/0304-3975(92)90232-5openalex-snapshot
Strong separations of the polynomial hierarchy with oracles: constructive separations by immune and simple sets
inferred← citeshttps://doi.org/10.1016/0304-3975(92)90317-9openalex-snapshot
On independent random oracles
inferred← citeshttps://doi.org/10.1016/0304-3975(93)90214-eopenalex-snapshot
Probabilistic polynomials, AC0 functions and the polynomial-time hierarchy
inferred← citeshttps://doi.org/10.1016/0304-3975(93)90256-sopenalex-snapshot
Circuit size relative to pseudorandom oracles
inferred← citeshttps://doi.org/10.1016/0304-3975(93)90258-uopenalex-snapshot
On read once vs. multiple access to randomness in logspace
inferred← citeshttps://doi.org/10.1016/0304-3975(94)00023-copenalex-snapshot
Almost every set in exponential time is P-bi-immune
inferred← citeshttps://doi.org/10.1016/0304-3975(96)89424-2openalex-snapshot
Genericity and measure for exponential time
inferred← citeshttps://doi.org/10.1016/0890-5401(87)90057-5openalex-snapshot
On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes
inferred← citeshttps://doi.org/10.1016/0890-5401(89)90020-5openalex-snapshot
Simplicity, immunity, relativizations and nondeterminism
inferred← citeshttps://doi.org/10.1016/0890-5401(92)90040-mopenalex-snapshot
Diagonalization, uniformity, and fixed-point theorems
inferred← citeshttps://doi.org/10.1016/0890-5401(92)90055-kopenalex-snapshot
Generic oracles, uniform machines, and codes
inferred← citeshttps://doi.org/10.1016/b978-0-12-386870-1.50024-1openalex-snapshot
On Probability that a Randomly Selected Set Has Some complexity-Theoretical Property
inferred← citeshttps://doi.org/10.1016/b978-0-444-88071-0.50007-2openalex-snapshot
A Catalog of Complexity Classes
inferred← citeshttps://doi.org/10.1016/b978-0-444-88071-0.50019-9openalex-snapshot
The Complexity of Finite Functions
inferred← citeshttps://doi.org/10.1016/j.ipl.2009.07.009openalex-snapshot
Structural properties of oracle classes
inferred← citeshttps://doi.org/10.1016/j.tcs.2005.03.055openalex-snapshot
Resource bounded immunity and simplicity
inferred← citeshttps://doi.org/10.1016/j.tcs.2005.11.033openalex-snapshot
Computational depth: Concept and applications
inferred← citeshttps://doi.org/10.1016/j.tcs.2006.01.025openalex-snapshot
Hausdorff dimension and oracle constructions
inferred← citeshttps://doi.org/10.1016/s0019-9958(82)80019-3openalex-snapshot
Robustness of probabilistic computational complexity classes under definitional perturbations
inferred← citeshttps://doi.org/10.1016/s0019-9958(83)80023-0openalex-snapshot
On the random oracle hypothesis
inferred← citeshttps://doi.org/10.1016/s0019-9958(83)80058-8openalex-snapshot
Relativizations comparing NP and exponential time
inferred← citeshttps://doi.org/10.1016/s0019-9958(85)80032-2openalex-snapshot
There is no polynomial deterministic space simulation of probabilistic space with a two-way random-tape generator
inferred← citeshttps://doi.org/10.1016/s0019-9958(86)80012-2openalex-snapshot
On relativized exponential and probabilistic complexity classes
inferred← citeshttps://doi.org/10.1016/s0019-9958(86)80020-1openalex-snapshot
On the power of two-way random generators and the impossibility of deterministic poly-space simulation
inferred← citeshttps://doi.org/10.1016/s0019-9958(86)80044-4openalex-snapshot
A decisive characterization of BPP
inferred← citeshttps://doi.org/10.1016/s0020-0190(99)00034-4openalex-snapshot
Relativized worlds with an infinite hierarchy
inferred← citeshttps://doi.org/10.1016/s0022-0000(03)00068-0openalex-snapshot
One-way permutations and self-witnessing languages
inferred← citeshttps://doi.org/10.1016/s0022-0000(05)80084-4openalex-snapshot
The random oracle hypothesis is false
showing the first 200 of 365 · page through all 365
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.