Easiness assumptions and hardness tests: Trading time for zero error

DOI10.1006/JCSS.2001.1763MaRDI QIDQ5956013zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Randomness vs time: Derandomization under a uniform assumption
• scientific article; zbMATH DE number 1789922
• Can every randomized algorithm be derandomized?
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• Derandomizing Arthur-Merlin games under uniform assumptions

Cites work

• BPP has subexponential time simulations unless EXPTIME has publishable proofs
• A general method to construct oracles realizing given relationships between complexity classes
• A Pseudorandom Generator from any One-way Function
• Circuit minimization problem
• Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses
• Hardness vs randomness
• scientific article; zbMATH DE number 1304314 (Why is no real title available?)
• scientific article; zbMATH DE number 2080255 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Natural proofs
• On Relativized Polynomial and Exponential Computations
• One way functions and pseudorandom generators
• Relativized polynomial hierarchies extending two levels

Cited in

(14)

• Randomness vs time: Derandomization under a uniform assumption
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• Mining circuit lower bound proofs for meta-algorithms
• A zero-one law for RP and derandomization of AM if NP is not small
• Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
• Fine-grained derandomization: from problem-centric to resource-centric complexity
• A remark on pseudo proof systems and hard instances of the satisfiability problem
• NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES
• Unions of disjoint NP-complete sets
• Pseudo-random generators for all hardnesses
• Constructive separations and their consequences
• On exponential-time hypotheses, derandomization, and circuit lower bounds
• Towards PNP from extended Frege lower bounds
• Relations between average-case and worst-case complexity

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5956013)