On the public citation graph

On Tally Relativizations of $BP$-Complexity Classes

https://doi.org/10.1137/0218031
0 signed · 37 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-16486-3_112openalex-snapshot
Probabilistic quantifiers, adversaries, and complexity classes : An overview
inferredcites →https://doi.org/10.1007/3-540-16486-3_87openalex-snapshot
Randomness, relativizations, and polynomial reducibilities
inferredcites →https://doi.org/10.1007/3-540-18625-5_67openalex-snapshot
Probabilistic quantifiers vs. distrustful adversaries
inferredcites →https://doi.org/10.1007/978-1-4684-9440-2openalex-snapshot
Measure Theory
inferredcites →https://doi.org/10.1016/0020-0190(82)90139-9openalex-snapshot
Some observations on the probabilistic algorithms and NP-hard problems
inferredcites →https://doi.org/10.1016/0020-0190(87)90036-6openalex-snapshot
Random oracles separate PSPACE from the polynomial-time hierarchy
inferredcites →https://doi.org/10.1016/0304-3975(76)90061-xopenalex-snapshot
The polynomial-time hierarchy
inferredcites →https://doi.org/10.1016/0304-3975(76)90062-1openalex-snapshot
Complete sets and the polynomial-time hierarchy
inferredcites →https://doi.org/10.1016/0304-3975(83)90020-8openalex-snapshot
Some consequences of non-uniform conditions on uniform classes
inferredcites →https://doi.org/10.1016/s0022-0000(05)80043-1openalex-snapshot
Hardness vs randomness
inferredcites →https://doi.org/10.1093/comjnl/12.1.28openalex-snapshot
Theory of Recursive Functions and Effective Computability
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.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/0216056openalex-snapshot
A Note on Randomized Polynomial Time
inferredcites →https://doi.org/10.1145/5925.5937openalex-snapshot
The polynomial-time hierarchy and sparse oracles
inferredcites →https://doi.org/10.1145/5925.5938openalex-snapshot
Relativizing complexity classes with 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/978-1-4613-3394-4_14openalex-snapshot
Measure One Results in Computational 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-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/bf01202283openalex-snapshot
Structural analysis of the complexity of inverse functions
inferred← citeshttps://doi.org/10.1007/bf02090773openalex-snapshot
Characterizing polynomial complexity classes by reducibilities
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(92)90317-9openalex-snapshot
On independent random oracles
inferred← citeshttps://doi.org/10.1016/0304-3975(93)90256-sopenalex-snapshot
Circuit size relative to pseudorandom oracles
inferred← citeshttps://doi.org/10.1016/s0304-3975(00)00323-6openalex-snapshot
Dot operators
inferred← citeshttps://doi.org/10.1109/ccc.1997.612298openalex-snapshot
The general notion of a dot-operator
inferred← citeshttps://doi.org/10.1109/sct.1990.113975openalex-snapshot
Circuit size relative to pseudorandom oracles
inferred← citeshttps://doi.org/10.1109/sct.1990.113978openalex-snapshot
On separating complexity classes
inferred← citeshttps://doi.org/10.1109/sct.1991.160238openalex-snapshot
Counting classes are at least as hard as the polynomial-time hierarchy
inferred← citeshttps://doi.org/10.1109/sct.1991.160261openalex-snapshot
A pseudorandom oracle characterization of BPP
inferred← citeshttps://doi.org/10.1137/0220015openalex-snapshot
Some Observations on Separating Complexity Classes
inferred← citeshttps://doi.org/10.1137/0221023openalex-snapshot
Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
inferred← citeshttps://doi.org/10.1137/0222065openalex-snapshot
A Pseudorandom Oracle Characterization of ${\text{BPP}}$
inferred← citeshttps://doi.org/10.1137/s0097539793238140openalex-snapshot
On Languages Reducible to Algorithmically Random Languages
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.