On the public citation graph

Randomness vs Time: Derandomization under a Uniform Assumption

https://doi.org/10.1006/jcss.2001.1780

0 signed · 117 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/jcss.1996.0032openalex-snapshot

Oracles and Queries That Are Sufficient for Exact Learning

inferredcites →https://doi.org/10.1006/jcss.1997.1494openalex-snapshot

Natural Proofs

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-61440-0_142openalex-snapshot

Hitting sets derandomize BPP

inferredcites →https://doi.org/10.1007/bf01200056openalex-snapshot

Non-deterministic exponential time has two-prover interactive protocols

inferredcites →https://doi.org/10.1007/bf01200430openalex-snapshot

Non-deterministic exponential time has two-prover interactive protocols

inferredcites →https://doi.org/10.1007/bf01275486openalex-snapshot

BPP has subexponential time simulations unlessEXPTIME has publishable proofs

inferredcites →https://doi.org/10.1007/bf01375474openalex-snapshot

Pseudorandom bits for constant depth circuits

inferredcites →https://doi.org/10.1007/bf02579323openalex-snapshot

One way functions and pseudorandom generators

inferredcites →https://doi.org/10.1016/0898-1221(96)87348-2openalex-snapshot

Pseudorandomness and cryptographic applications

inferredcites →https://doi.org/10.1016/s0022-0000(05)80043-1openalex-snapshot

Hardness vs randomness

inferredcites →https://doi.org/10.1016/s0304-3975(99)00024-9openalex-snapshot

Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs

inferredcites →https://doi.org/10.1090/dimacs/002openalex-snapshot

Distributed Computing and Cryptography

inferredcites →https://doi.org/10.1090/dimacs/002/13openalex-snapshot

New directions in testing

inferredcites →https://doi.org/10.1109/sfcs.1982.45openalex-snapshot

Theory and application of trapdoor functions

inferredcites →https://doi.org/10.1109/sfcs.1982.95openalex-snapshot

Theory and application of trapdoor functions

inferredcites →https://doi.org/10.1109/sfcs.1995.492584openalex-snapshot

Hard-core distributions for somewhat hard problems

inferredcites →https://doi.org/10.1109/sffcs.1999.814590openalex-snapshot

Near-optimal conversion of hardness into pseudo-randomness

inferredcites →https://doi.org/10.1137/0213053openalex-snapshot

How to Generate Cryptographically Strong Sequences of Pseudorandom Bits

inferredcites →https://doi.org/10.1137/0215020openalex-snapshot

Average Case Complete Problems

inferredcites →https://doi.org/10.1137/0220053openalex-snapshot

PP is as Hard as the Polynomial-Time Hierarchy

inferredcites →https://doi.org/10.1137/0222069openalex-snapshot

On the Existence of Pseudorandom Generators

inferredcites →https://doi.org/10.1137/s0097539793244708openalex-snapshot

A Pseudorandom Generator from any One-way Function

inferredcites →https://doi.org/10.1137/s0097539797325636openalex-snapshot

Weak Random Sources, Hitting Sets, and BPP Simulations

inferredcites →https://doi.org/10.1145/273865.273933openalex-snapshot

A new general derandomization method

inferredcites →https://doi.org/10.1145/335305.335306openalex-snapshot

Extractors and pseudo-random generators with optimal seed length

inferredcites →https://doi.org/10.1145/357353.357357openalex-snapshot

On the generation of cryptographically strong pseudorandom sequences

inferredcites →https://doi.org/10.1145/73007.73010openalex-snapshot

A hard-core predicate for all one-way functions

inferredcites →https://doi.org/10.1515/9780691206844openalex-snapshot

Pseudorandomness and Cryptographic Applications

inferredcites →https://doi.org/10.5169/seals-52237openalex-snapshot

TURING MACHINES THAT TAKE ADVICE

What points at this work

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

inferred← citeshttps://doi.org/10.1007/11776420_27openalex-snapshot

Efficient Learning Algorithms Yield Circuit Lower Bounds

inferred← citeshttps://doi.org/10.1007/3-540-36494-3_20openalex-snapshot

Some Results on Derandomization

inferred← citeshttps://doi.org/10.1007/3-540-49116-3_8openalex-snapshot

On the Hardness of Permanent

inferred← citeshttps://doi.org/10.1007/978-3-030-43662-9_15openalex-snapshot

Worst-Case to Average-Case Reductions for Subclasses of P

inferred← citeshttps://doi.org/10.1007/978-3-030-43662-9_4openalex-snapshot

Two Comments on Targeted Canonical Derandomizers

inferred← citeshttps://doi.org/10.1007/978-3-540-85363-3_37openalex-snapshot

Limitations of Hardness vs. Randomness under Uniform Reductions

inferred← citeshttps://doi.org/10.1007/978-3-642-03685-9_43openalex-snapshot

Pseudorandom Generators and Typically-Correct Derandomization

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/978-3-642-22006-7_25openalex-snapshot

Limits on the Computational Power of Random Strings

inferred← citeshttps://doi.org/10.1007/978-3-642-22670-0_20openalex-snapshot

In a World of P=BPP

inferred← citeshttps://doi.org/10.1007/978-3-642-22935-0_32openalex-snapshot

Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification

inferred← citeshttps://doi.org/10.1007/978-3-642-38233-8_16openalex-snapshot

Succinct Permanent Is NEXP-Hard with Many Hard Instances

inferred← citeshttps://doi.org/10.1007/s00037-004-0182-6openalex-snapshot

Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds

inferred← citeshttps://doi.org/10.1007/s00037-007-0232-yopenalex-snapshot

Special Issue On Worst-case Versus Average-case Complexity Editors’ Foreword

inferred← citeshttps://doi.org/10.1007/s00037-007-0233-xopenalex-snapshot

Pseudorandomness and Average-Case Complexity Via Uniform Reductions

inferred← citeshttps://doi.org/10.1007/s00037-007-0235-8openalex-snapshot

If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances

inferred← citeshttps://doi.org/10.1007/s00037-011-0006-4openalex-snapshot

Weak Derandomization of Weak Algorithms: Explicit Versions of Yao’s Lemma

inferred← citeshttps://doi.org/10.1007/s00037-011-0019-zopenalex-snapshot

Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds

inferred← citeshttps://doi.org/10.1007/s00037-014-0087-yopenalex-snapshot

On Uniformity and Circuit Lower Bounds

inferred← citeshttps://doi.org/10.1007/s00037-016-0128-9openalex-snapshot

Incompressible Functions, Relative-Error Extractors, and the Power of Nondeterministic Reductions

inferred← citeshttps://doi.org/10.1007/s00037-024-00260-5openalex-snapshot

On the Structure of Learnability beyond P/poly

inferred← citeshttps://doi.org/10.1007/s00037-025-00279-2openalex-snapshot

Instance-Wise Hardness and Refutation versus Derandomization for Arthur-Merlin Protocols

inferred← citeshttps://doi.org/10.1007/s00493-006-0036-8openalex-snapshot

Reducing The Seed Length In The Nisan-Wigderson Generator*

inferred← citeshttps://doi.org/10.1016/j.ic.2011.09.008openalex-snapshot

Limits on the computational power of random strings

inferred← citeshttps://doi.org/10.1016/j.ipl.2011.01.019openalex-snapshot

A zero-one SUBEXP-dimension law for BPP

inferred← citeshttps://doi.org/10.1016/j.jcss.2008.07.006openalex-snapshot

Efficient learning algorithms yield circuit lower bounds

inferred← citeshttps://doi.org/10.1016/j.jcss.2010.06.004openalex-snapshot

The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory

inferred← citeshttps://doi.org/10.1016/j.tcs.2004.02.029openalex-snapshot

The size of SPP

inferred← citeshttps://doi.org/10.1016/j.tcs.2018.04.038openalex-snapshot

Circuit lower bounds from learning-theoretic approaches

inferred← citeshttps://doi.org/10.1090/ulect/055openalex-snapshot

A Primer on Pseudorandom Generators

inferred← citeshttps://doi.org/10.1098/rsta.2011.0318openalex-snapshot

Uniform derandomization from pathetic lower bounds

inferred← citeshttps://doi.org/10.1109/ccc.2003.1214427openalex-snapshot

Holographic proofs and derandomization

inferred← citeshttps://doi.org/10.1109/ccc.2009.27openalex-snapshot

Weak Derandomization of Weak Algorithms: Explicit Versions of Yao's Lemma

inferred← citeshttps://doi.org/10.1109/ccc.2013.40openalex-snapshot

On Medium-Uniformity and Circuit Lower Bounds

inferred← citeshttps://doi.org/10.1109/focs.2004.33openalex-snapshot

Hierarchy Theorems for Probabilistic Polynomial Time

inferred← citeshttps://doi.org/10.1109/focs.2006.13openalex-snapshot

Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification

inferred← citeshttps://doi.org/10.1109/focs.2018.00017openalex-snapshot

Counting t-Cliques: Worst-Case to Average-Case Reductions and Direct Interactive Proof Systems

inferred← citeshttps://doi.org/10.1109/focs.2018.00032openalex-snapshot

Non-Black-Box Worst-Case to Average-Case Reductions within NP

inferred← citeshttps://doi.org/10.1109/focs52979.2021.00062openalex-snapshot

Quantum learning algorithms imply circuit lower bounds

inferred← citeshttps://doi.org/10.1109/focs52979.2021.00069openalex-snapshot

Constructive Separations and Their Consequences

inferred← citeshttps://doi.org/10.1109/focs54457.2022.00058openalex-snapshot

Hardness Self-Amplification from Feasible Hard-Core Sets

inferred← citeshttps://doi.org/10.1109/focs54457.2022.00067openalex-snapshot

On the Range Avoidance Problem for Circuits

inferred← citeshttps://doi.org/10.1109/focs57990.2023.00062openalex-snapshot

Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization

inferred← citeshttps://doi.org/10.1109/focs57990.2023.00074openalex-snapshot

Polynomial-Time Pseudodeterministic Construction of Primes

inferred← citeshttps://doi.org/10.1109/focs61266.2024.00140openalex-snapshot

On the Complexity of Avoiding Heavy Elements

inferred← citeshttps://doi.org/10.1137/050628994openalex-snapshot

Power from Random Strings

inferred← citeshttps://doi.org/10.1137/070683994openalex-snapshot

Approximate List-Decoding of Direct Product Codes and Uniform Hardness Amplification

inferred← citeshttps://doi.org/10.1137/080735096openalex-snapshot

Hardness Amplification Proofs Require Majority

inferred← citeshttps://doi.org/10.1137/130938219openalex-snapshot

Natural Proofs versus Derandomization

inferred← citeshttps://doi.org/10.1137/17m1145707openalex-snapshot

Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace

inferred← citeshttps://doi.org/10.1137/19m124705xopenalex-snapshot

Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)

inferred← citeshttps://doi.org/10.1137/s0097539703438629openalex-snapshot

Holographic Proofs and Derandomization

inferred← citeshttps://doi.org/10.1137/s0097539705447281openalex-snapshot

Using Nondeterminism to Amplify Hardness

inferred← citeshttps://doi.org/10.1145/1007352.1007389openalex-snapshot

Using nondeterminism to amplify hardness

inferred← citeshttps://doi.org/10.1145/1086649.1086662openalex-snapshot

SIGACT news complexity theory column 48

inferred← citeshttps://doi.org/10.1145/1107523.1107535openalex-snapshot

SIGACT news complexity theory column 49

inferred← citeshttps://doi.org/10.1145/1814370.1814389openalex-snapshot

Typically-correct derandomization

inferred← citeshttps://doi.org/10.1145/1993574.1993592openalex-snapshot

Repeated matching pennies with limited randomness

inferred← citeshttps://doi.org/10.1145/2488608.2488612openalex-snapshot

Natural proofs versus derandomization

inferred← citeshttps://doi.org/10.1145/2591508openalex-snapshot

Unions of Disjoint NP-Complete Sets

inferred← citeshttps://doi.org/10.1145/2840728.2840745openalex-snapshot

Time-Lock Puzzles from Randomized Encodings

inferred← citeshttps://doi.org/10.1145/3055399.3055500openalex-snapshot

Pseudodeterministic constructions in subexponential time

inferred← citeshttps://doi.org/10.1145/3313276.3316348openalex-snapshot

Static data structure lower bounds imply rigidity

inferred← citeshttps://doi.org/10.1145/3357713.3384251openalex-snapshot

Unexpected hardness results for Kolmogorov complexity under uniform reductions

inferred← citeshttps://doi.org/10.1145/3406325.3451085openalex-snapshot

Pseudodeterministic algorithms and the structure of probabilistic time

inferred← citeshttps://doi.org/10.1145/3538391openalex-snapshot

Beyond Natural Proofs: Hardness Magnification and Locality

inferred← citeshttps://doi.org/10.1145/3564246.3585130openalex-snapshot

Capturing One-Way Functions via NP-Hardness of Meta-Complexity

inferred← citeshttps://doi.org/10.1145/3618260.3649784openalex-snapshot

On the Power of Interactive Proofs for Learning

inferred← citeshttps://doi.org/10.1145/3717823.3718224openalex-snapshot

Maximum Circuit Lower Bounds for Exponential-Time Arthur Merlin

inferred← citeshttps://doi.org/10.1145/3798129.3800867openalex-snapshot

Failure of Symmetry of Information for Randomized Computations

inferred← citeshttps://doi.org/10.1145/3803408openalex-snapshot

Polynomial-Time Pseudodeterministic Construction of Primes

inferred← citeshttps://doi.org/10.1145/504192.504194openalex-snapshot

SIGACT News complexity theory column 32

inferred← citeshttps://doi.org/10.1515/9783110203738.455openalex-snapshot

Chapter 8 Notes and References

inferred← citeshttps://doi.org/10.15276/eltecs.30.106.2019.22openalex-snapshot

MATHEMATICAL FOUNDATION OF INFORMATION TECHNOLOGIES IN MODERN NONLINEAR DYNAMICAL SYSTEMS

inferred← citeshttps://doi.org/10.1561/0400000010openalex-snapshot

Pseudorandomness

inferred← citeshttps://doi.org/10.1561/0400000109openalex-snapshot

Paradigms for Unconditional Pseudorandom Generators

inferred← citeshttps://doi.org/10.18725/oparu-3883openalex-snapshot

Derandomizing RP if Boolean circuits are not learnable

inferred← citeshttps://doi.org/10.37236/551openalex-snapshot

Lower Bounds on van der Waerden Numbers: Randomized- and Deterministic-Constructive

inferred← citeshttps://doi.org/10.4230/lipics.ccc.2016.10openalex-snapshot

Learning Algorithms from Natural Proofs

inferred← citeshttps://doi.org/10.46298/theoretics.24.3openalex-snapshot

Constructive Separations and Their Consequences

inferred← citeshttps://doi.org/10.48550/arxiv.1005.3749openalex-snapshot

Lower Bounds on the van der Waerden Numbers: Randomized- and Deterministic-Constructive

inferred← citeshttps://doi.org/10.48550/arxiv.1102.1096openalex-snapshot

Repeated Matching Pennies with Limited Randomness

inferred← citeshttps://doi.org/10.48550/arxiv.cs/0304040openalex-snapshot

Hardness as randomness: a survey of universal derandomization

inferred← citeshttps://doi.org/10.5446/15981openalex-snapshot

P, NP and mathematics - a computational complexity perspective

inferred← citeshttps://doi.org/10.7282/t32b8wngopenalex-snapshot

Some applications of randomness in computational complexity

inferred← citeshttps://doi.org/10.7282/t35d8qvqopenalex-snapshot

On circuit complexity classes and iterated matrix multiplication

inferred← citeshttps://doi.org/10.7916/d8zp45ktopenalex-snapshot

Unconditional Lower Bounds in Complexity Theory

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.