scientific article; zbMATH DE number 1104167

MaRDI QIDQ4370034zbMATH OpenFDO

Authors Vikraman Arvind, Johannes Köbler

Publication date 25 May 1998

zbMATH Keywords

BPNPpseudorandomnessresource-bounded measure theory

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On pseudorandomness and resource-bounded measure
• scientific article; zbMATH DE number 1048036
• Resource bounded randomness and computational complexity
• scientific article; zbMATH DE number 1492083
• On a connection between pseudorandom measures
• scientific article; zbMATH DE number 2208523
• Resource bounded randomness and weakly complete problems
• scientific article; zbMATH DE number 1555954
• Sub-computable bounded pseudorandomness
• Pseudorandom bits and lower bounds for randomized Turing machines

Cited in

(10)

• New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes.
• How strong is Nisan's pseudo-random generator?
• Polylog depth, highness and lowness for E
• A zero-one law for RP and derandomization of AM if NP is not small
• A classification of the probabilistic polynomial time hierarchy under fault tolerant access to oracle classes
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• On pseudorandomness and resource-bounded measure
• Pseudorandom generators without the XOR lemma
• Nearly optimal pseudorandomness from hardness
• \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)

This page was built for publication:

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