Structural complexity of AvgBPP

DOI10.1016/J.APAL.2010.09.006MaRDI QIDQ638488zbMATH OpenOpenAlexFDO

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

Recommendations

• Structural Complexity of AvgBPP
• On the theory of average case complexity
• Fine separation of average time complexity classes
• Structural average case complexity
• Fine Separation of Average-Time Complexity Classes

Cites work

• scientific article; zbMATH DE number 5081744 (Why is no real title available?)
• scientific article; zbMATH DE number 4070309 (Why is no real title available?)
• scientific article; zbMATH DE number 4091486 (Why is no real title available?)
• scientific article; zbMATH DE number 176768 (Why is no real title available?)
• scientific article; zbMATH DE number 2019635 (Why is no real title available?)
• A Complete Public-Key Cryptosystem
• A generic time hierarchy with one bit of advice
• Average Case Complete Problems
• On Robust Combiners for Oblivious Transfer and Other Primitives
• On the theory of average case complexity

Cited in

(3)

• On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography
• Complete problems with L-samplable distributions
• Structural Complexity of AvgBPP

This page was built for publication: Structural complexity of AvgBPP

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