On the public citation graph

On resource-bounded measure and pseudorandomness

https://doi.org/10.1007/bfb0058034
0 signed · 67 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-10843-2_43openalex-snapshot
On the generation of cryptographically strong pseudo-random sequences
inferredcites →https://doi.org/10.1007/3-540-18625-5_67openalex-snapshot
Probabilistic quantifiers vs. distrustful adversaries
inferredcites →https://doi.org/10.1007/3-540-61440-0_142openalex-snapshot
Hitting sets derandomize BPP
inferredcites →https://doi.org/10.1007/3-540-63165-8_175openalex-snapshot
Worst-case hardness suffices for derandomization: A new method for hardness-randomness trade-offs
inferredcites →https://doi.org/10.1007/3-540-63248-4_8openalex-snapshot
Super-bits, demi-bits, and NP/qpoly-natural proofs
inferredcites →https://doi.org/10.1007/978-3-642-75357-2openalex-snapshot
Structural Complexity II
inferredcites →https://doi.org/10.1007/978-3-642-79235-9openalex-snapshot
Structural Complexity I
inferredcites →https://doi.org/10.1007/bf02679469openalex-snapshot
Observations on measure and lowness for Δ 2 P
inferredcites →https://doi.org/10.1007/s002240000060openalex-snapshot
Observations on Measure and Lowness for Δ P_2
inferredcites →https://doi.org/10.1016/0022-0000(89)90020-2openalex-snapshot
Probabilistic complexity classes and lowness
inferredcites →https://doi.org/10.1016/0022-0000(89)90024-xopenalex-snapshot
PNP[(log )] and sparse turing-complete sets for NP
inferredcites →https://doi.org/10.1016/0022-0000(92)90020-jopenalex-snapshot
Almost everywhere high nonuniform complexity
inferredcites →https://doi.org/10.1016/0304-3975(93)90256-sopenalex-snapshot
Circuit size relative to pseudorandom oracles
inferredcites →https://doi.org/10.1016/0304-3975(95)00189-1openalex-snapshot
Cook versus Karp-Levin: Separating completeness notions if NP is not small
inferredcites →https://doi.org/10.1016/0890-5401(89)90022-9openalex-snapshot
Relativized Arthur-Merlin versus Merlin-Arthur games
inferredcites →https://doi.org/10.1016/s0022-0000(05)80043-1openalex-snapshot
Hardness vs randomness
inferredcites →https://doi.org/10.1109/sfcs.1982.45openalex-snapshot
Theory and application of trapdoor functions
inferredcites →https://doi.org/10.1109/sfcs.1994.365713openalex-snapshot
Measure on small complexity classes, with applications for BPP
inferredcites →https://doi.org/10.1137/0220053openalex-snapshot
PP is as Hard as the Polynomial-Time Hierarchy
inferredcites →https://doi.org/10.1137/0222065openalex-snapshot
A Pseudorandom Oracle Characterization of ${\text{BPP}}$
inferredcites →https://doi.org/10.1137/s0097539792228289openalex-snapshot
The Complexity of Decision Versus Search
inferredcites →https://doi.org/10.1145/22145.22192openalex-snapshot
Trading group theory for randomness
inferredcites →https://doi.org/10.1145/258533.258590openalex-snapshot
P = BPP if E requires exponential circuits
inferredcites →https://doi.org/10.1145/3149.3158openalex-snapshot
A complexity theory based on Boolean algebra
inferredcites →https://doi.org/10.1145/800141.804678openalex-snapshot
Some connections between nonuniform and uniform complexity classes

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1006/jcss.2000.1730openalex-snapshot
Pseudorandom Generators without the XOR Lemma
inferred← citeshttps://doi.org/10.1007/11494645_61openalex-snapshot
Arthur-Merlin Games and the Problem of Isomorphism Testing
inferred← citeshttps://doi.org/10.1007/3-540-45655-4_4openalex-snapshot
On Higher Arthur-Merlin Classes
inferred← citeshttps://doi.org/10.1007/3-540-45726-7_17openalex-snapshot
Derandomization That Is Rarely Wrong from Short Advice That Is Typically Good
inferred← citeshttps://doi.org/10.1007/3-540-46541-3_36openalex-snapshot
Graph Isomorphism Is Low for ZPP(NP) and Other Lowness Results
inferred← citeshttps://doi.org/10.1007/3-540-48224-5_28openalex-snapshot
On Interactive Proofs with a Laconic Prover
inferred← citeshttps://doi.org/10.1007/3-540-48686-0_21openalex-snapshot
Super-Polynomial Versus Half-Exponential Circuit Size in the Exponential Hierarchy
inferred← citeshttps://doi.org/10.1007/978-3-642-15369-3_29openalex-snapshot
Uniform Derandomization from Pathetic Lower Bounds
inferred← citeshttps://doi.org/10.1007/bfb0055799openalex-snapshot
Average-case intractability vs. worst-case intractability
inferred← citeshttps://doi.org/10.1007/bfb0058017openalex-snapshot
Foundations of Software Technology and Theoretical Computer Science
inferred← citeshttps://doi.org/10.1007/s00037-002-0169-0openalex-snapshot
On interactive proofs with a laconic prover
inferred← citeshttps://doi.org/10.1007/s00037-003-0178-7openalex-snapshot
Uniform hardness versus randomness tradeoffs for Arthur-Merlin games
inferred← citeshttps://doi.org/10.1016/j.ic.2009.02.002openalex-snapshot
A zero-one law for RP and derandomization of AM if NP is not small
inferred← citeshttps://doi.org/10.1016/j.ic.2019.104483openalex-snapshot
Polylog depth, highness and lowness for E
inferred← citeshttps://doi.org/10.1016/j.jcss.2003.07.015openalex-snapshot
S2p⊆ZPPNP
inferred← citeshttps://doi.org/10.1016/s0304-3975(99)00164-4openalex-snapshot
On pseudorandomness and resource-bounded measure
inferred← citeshttps://doi.org/10.1090/pcms/010/10openalex-snapshot
Pseudorandomness—Part II
inferred← citeshttps://doi.org/10.1098/rsta.2011.0318openalex-snapshot
Uniform derandomization from pathetic lower bounds
inferred← citeshttps://doi.org/10.1109/ccc.1998.694603openalex-snapshot
On the resource bounded measure of P/poly
inferred← citeshttps://doi.org/10.1109/ccc.2003.1214408openalex-snapshot
Uniform hardness vs. randomness tradeoffs for Arthur-Merlin games
inferred← citeshttps://doi.org/10.1109/ccc.2003.1214409openalex-snapshot
A zero one law for RP
inferred← citeshttps://doi.org/10.1109/ccc.2004.1313808openalex-snapshot
Solvable group isomorphism is (almost) in NP ∩ coNP
inferred← citeshttps://doi.org/10.1109/ccc.2004.33openalex-snapshot
Solvable Group Isomorphism is (almost) in NP CoNP
inferred← citeshttps://doi.org/10.1109/ccc.2006.26openalex-snapshot
Making Hard Problems Harder
inferred← citeshttps://doi.org/10.1109/focs46700.2020.00102openalex-snapshot
Nearly Optimal Pseudorandomness From Hardness
inferred← citeshttps://doi.org/10.1109/sfcs.2000.892063openalex-snapshot
Extracting randomness from samplable distributions
inferred← citeshttps://doi.org/10.1109/sfcs.2001.959941openalex-snapshot
Simple extractors for all min-entropies and a new pseudo-random generator
inferred← citeshttps://doi.org/10.1109/sffcs.1999.814579openalex-snapshot
Derandomizing Arthur-Merlin games using hitting sets
inferred← citeshttps://doi.org/10.1145/1059513.1059516openalex-snapshot
Simple extractors for all min-entropies and a new pseudorandom generator
inferred← citeshttps://doi.org/10.1145/1250790.1250832openalex-snapshot
Circuit lower bounds for Merlin-Arthur classes
inferred← citeshttps://doi.org/10.1145/1944857.1944859openalex-snapshot
Solvable Group Isomorphism Is (Almost) in NP ∩ coNP
inferred← citeshttps://doi.org/10.1145/301250.301397openalex-snapshot
Pseudorandom generators without the XOR Lemma (extended abstract)
inferred← citeshttps://doi.org/10.1145/335305.335330openalex-snapshot
On transformation of interactive proofs that preserve the prover's complexity
inferred← citeshttps://doi.org/10.1145/335305.335357openalex-snapshot
Are bitvectors optimal?
inferred← citeshttps://doi.org/10.1145/3406325.3451116openalex-snapshot
Fiat–Shamir via list-recoverable codes (or: parallel repetition of GMW is not zero-knowledge)
inferred← citeshttps://doi.org/10.1145/3555307openalex-snapshot
Nearly Optimal Pseudorandomness from Hardness
inferred← citeshttps://doi.org/10.1145/502090.502099openalex-snapshot
Extractors and pseudorandom generators
inferred← citeshttps://doi.org/10.48550/arxiv.1602.03332openalex-snapshot
Polynomial Depth, Highness and Lowness for E
inferred← citeshttps://doi.org/10.7146/brics.v6i46.20116openalex-snapshot
Super-Polynomial Versus Half-Exponential Circuit Size in the Exponential Hierarchy
inferred← citeshttps://doi.org/10.7146/brics.v6i47.20117openalex-snapshot
Derandomizing Arthur-Merlin Games using Hitting Sets
inferred← citeshttps://doi.org/10.7282/t35d8qvqopenalex-snapshot
On circuit complexity classes and iterated matrix multiplication
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.