On the public citation graph

Easiness Assumptions and Hardness Tests: Trading Time for Zero Error

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

0 signed · 80 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.1997.1494openalex-snapshot

Natural Proofs

inferredcites →https://doi.org/10.1007/3-540-40996-3_26openalex-snapshot

Derandomizing Arthur-Merlin Games under Uniform Assumptions

inferredcites →https://doi.org/10.1007/3-540-49116-3_9openalex-snapshot

One-Sided Versus Two-Sided Error in Probabilistic Computation

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

BPP has subexponential time simulations unlessEXPTIME has publishable proofs

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

Relativized polynomial hierarchies extending two levels

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

One way functions and pseudorandom generators

inferredcites →https://doi.org/10.1016/0096-0551(80)90011-9openalex-snapshot

Introduction to automata theory, languages, and computation

inferredcites →https://doi.org/10.1016/0304-3975(95)00161-1openalex-snapshot

A general method to construct oracles realizing given relationships between complexity classes

inferredcites →https://doi.org/10.1016/0378-4754(81)90068-9openalex-snapshot

Introduction to automata theory, languages and computation

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

Hardness vs randomness

inferredcites →https://doi.org/10.1017/cbo9780511814075openalex-snapshot

Randomized Algorithms

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

Theory and application of trapdoor functions

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

Randomness vs. time: de-randomization under a uniform assumption

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

On Relativized Polynomial and Exponential Computations

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

Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses

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

A Pseudorandom Generator from any One-way Function

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

P = BPP if E requires exponential circuits

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

Proceedings of the thirty-first annual ACM symposium on Theory of Computing

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

Proceedings of the thirty-second annual ACM symposium on Theory of computing

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

Circuit minimization problem

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

A hard-core predicate for all one-way functions

What points at this work

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

inferred← citeshttps://doi.org/10.1002/malq.201700009openalex-snapshot

A remark on pseudo proof systems and hard instances of the satisfiability problem

inferred← citeshttps://doi.org/10.1007/11537311_37openalex-snapshot

Relations Between Average-Case and Worst-Case Complexity

inferred← citeshttps://doi.org/10.1007/11590156_2openalex-snapshot

Computational Complexity Since 1980

inferred← citeshttps://doi.org/10.1007/11830924_36openalex-snapshot

Worst-Case Vs. Algorithmic Average-Case Complexity in the Polynomial-Time Hierarchy

inferred← citeshttps://doi.org/10.1007/11944836_19openalex-snapshot

Some Results on Average-Case Hardness Within the Polynomial Hierarchy

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/978-3-540-30538-5_28openalex-snapshot

Hardness Hypotheses, Derandomization, and Circuit Complexity

inferred← citeshttps://doi.org/10.1007/978-3-540-74208-1_41openalex-snapshot

Worst-Case to Average-Case Reductions Revisited

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-22006-7_48openalex-snapshot

Robust Simulations and Significant Separations

inferred← citeshttps://doi.org/10.1007/978-981-99-3761-5_57openalex-snapshot

A Brief Overview of Randomized Algorithms

inferred← citeshttps://doi.org/10.1007/s00037-005-0197-7openalex-snapshot

Derandomizing Arthur–Merlin Games using Hitting Sets

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-0019-zopenalex-snapshot

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

inferred← citeshttps://doi.org/10.1007/s00037-015-0100-0openalex-snapshot

Mining Circuit Lower Bound Proofs for Meta-Algorithms

inferred← citeshttps://doi.org/10.1007/s00224-007-9071-0openalex-snapshot

Relations between Average-Case and Worst-Case Complexity

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.2017.07.002openalex-snapshot

Robust simulations and significant separations

inferred← citeshttps://doi.org/10.1016/s0022-0000(02)00024-7openalex-snapshot

In search of an easy witness: exponential time vs. probabilistic polynomial time

inferred← citeshttps://doi.org/10.1016/s0022-0000(03)00046-1openalex-snapshot

Pseudo-random generators for all hardnesses

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

Pseudorandomness and average-case complexity via uniform reductions

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

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

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

Making Hard Problems Harder

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

Minimizing DNF Formulas and AC^0_d Circuits Given a Truth Table

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

Mining Circuit Lower Bound Proofs for Meta-algorithms

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

Hardness Magnification for Natural Problems

inferred← citeshttps://doi.org/10.1109/focs46700.2020.00009openalex-snapshot

Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization

inferred← citeshttps://doi.org/10.1109/focs46700.2020.00010openalex-snapshot

On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds: Extended Abstract

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

Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise

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

The Hardest Explicit Construction

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

Constructive Separations and Their Consequences

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

LEARN-Uniform Circuit Lower Bounds and Provability in Bounded Arithmetic

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

Unstructured Hardness to Average-Case Randomness

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/sfcs.2002.1181992openalex-snapshot

Power from random strings

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

Power from Random Strings

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

Low-End Uniform Hardness versus Randomness Tradeoffs for AM

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

Natural Proofs versus Derandomization

inferred← citeshttps://doi.org/10.1137/22m1475491openalex-snapshot

Hardness vs. Randomness, Revised: Uniform, Non-Black-Box, and Instance-wise

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

Holographic Proofs and Derandomization

inferred← citeshttps://doi.org/10.1142/9789812562494_0012openalex-snapshot

DERANDOMIZATION: A BRIEF OVERVIEW

inferred← citeshttps://doi.org/10.1142/s0129054105003819openalex-snapshot

NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES

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

Typically-correct derandomization

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/3055399.3055500openalex-snapshot

Pseudodeterministic constructions in subexponential time

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

On Exponential-time Hypotheses, Derandomization, and Circuit Lower Bounds

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

Fiat-Shamir in the Plain Model from Derandomization (Or: Do Efficient Algorithms Believe that NP = PSPACE?)

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

Student-Teacher Constructive Separations and (Un)Provability in Bounded Arithmetic: Witnessing the Gap

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

Towards P≠NP from Extended Frege lower bounds

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

Pseudo-random generators for all hardnesses

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

Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness

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

Constructive Separations and Their Consequences

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

Robust Simulations and Significant Separations

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

Natural Proofs Versus Derandomization

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

Some Results on Circuit Lower Bounds and Derandomization of Arthur-Merlin Problems

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

Hardness as randomness: a survey of universal derandomization

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.