Structural complexity of AvgBPP

DOI10.1016/J.APAL.2010.09.006zbMATH Open1221.68093OpenAlexW1979324521MaRDI QIDQ638488FDOQ638488

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

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

zbMATH Keywords

randomized algorithmsaverage-case complexityBPPcomplete problemserrorless heuristicstime hierarchy

Mathematics Subject Classification ID

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

Cites Work

• On the theory of average case complexity
• Title not available (Why is that?)
• A Complete Public-Key Cryptosystem
• Average Case Complete Problems
• On Robust Combiners for Oblivious Transfer and Other Primitives
• Title not available (Why is that?)
• Title not available (Why is that?)
• A generic time hierarchy with one bit of advice
• Title not available (Why is that?)
• Title not available (Why is that?)

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)