Easiness assumptions and hardness tests: Trading time for zero error

DOI10.1006/jcss.2001.1763zbMath0988.68221OpenAlexW2021652795MaRDI QIDQ5956013

Valentine Kabanets

Publication date: 22 July 2002

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/491ad6d93839b13330fed4243c9a4b685fdd6610

zbMATH Keywords

BPP algorithmsRP algorithm

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Related Items (12)

In search of an easy witness: Exponential time vs. probabilistic polynomial time. ⋮ A zero-one law for RP and derandomization of AM if NP is not small ⋮ Robust simulations and significant separations ⋮ A remark on pseudo proof systems and hard instances of the satisfiability problem ⋮ Unnamed Item ⋮ Pseudorandom generators, typically-correct derandomization, and circuit lower bounds ⋮ Relations between average-case and worst-case complexity ⋮ NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES ⋮ Pseudo-random generators for all hardnesses ⋮ Natural Proofs versus Derandomization ⋮ Unions of Disjoint NP-Complete Sets ⋮ Mining circuit lower bound proofs for meta-algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• One way functions and pseudorandom generators
• \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
• Hardness vs randomness
• A general method to construct oracles realizing given relationships between complexity classes
• Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses
• Circuit minimization problem
• Relativized polynomial hierarchies extending two levels
• On Relativized Polynomial and Exponential Computations
• A Pseudorandom Generator from any One-way Function
• Natural proofs

This page was built for publication: Easiness assumptions and hardness tests: Trading time for zero error