Structural complexity of AvgBPP

DOI10.1016/j.apal.2010.09.006zbMath1221.68093OpenAlexW1979324521MaRDI QIDQ638488

Dmitry Itsykson

Publication date: 12 September 2011

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2010.09.006

zbMATH Keywords

randomized algorithmsaverage-case complexityBPPcomplete problemserrorless heuristicstime hierarchy

Mathematics Subject Classification ID

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

Related Items (2)

On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography ⋮ Structural Complexity of AvgBPP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the theory of average case complexity
• A generic time hierarchy with one bit of advice
• A Complete Public-Key Cryptosystem
• Average Case Complete Problems
• On Robust Combiners for Oblivious Transfer and Other Primitives

This page was built for publication: Structural complexity of AvgBPP