On pseudorandomness and resource-bounded measure

DOI10.1016/S0304-3975(99)00164-4zbMath0974.68063MaRDI QIDQ5941070

V. Arvind, Johannes Köbler

Publication date: 20 August 2001

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

derandomizationprobabilistic complexity classespseudorandom generatorresource bounded measure

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (11)

The size of SPP ⋮ Average-case intractability vs. worst-case intractability ⋮ The power of natural properties as oracles ⋮ Arthur and Merlin as oracles ⋮ ON HIGHER ARTHUR-MERLIN CLASSES ⋮ NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES ⋮ Lower bounds for non-black-box zero knowledge ⋮ Dimension, entropy rates, and compression ⋮ Efficient learning algorithms yield circuit lower bounds ⋮ Unnamed Item ⋮ The complexity of estimating min-entropy

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Cook versus Karp-Levin: Separating completeness notions if NP is not small
• \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP]
• Relativized circuit complexity
• Relativized Arthur-Merlin versus Merlin-Arthur games
• Almost everywhere high nonuniform complexity
• Circuit size relative to pseudorandom oracles
• Probabilistic complexity classes and lowness
• Hardness vs randomness
• Observations on measure and lowness for \(\Delta_ 2^ p\)
• PP is closed under truth-table reductions
• Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs
• A Pseudorandom Oracle Characterization of ${\text{BPP}}$
• PP is as Hard as the Polynomial-Time Hierarchy
• A complexity theory based on Boolean algebra
• The Complexity of Decision Versus Search

This page was built for publication: On pseudorandomness and resource-bounded measure