Structural Complexity of AvgBPP

DOI10.1007/978-3-642-03351-3_16MaRDI QIDQ3392950zbMATH OpenOpenAlexFDO

Authors Dmitry Itsykson

Publication date 18 August 2009

Published in Computer Science - Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-03351-3_16

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

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

• A Complete Public-Key Cryptosystem
• A generic time hierarchy with one bit of advice
• Average Case Complete Problems
• Average-Case Complexity
• 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?)
• On Robust Combiners for Oblivious Transfer and Other Primitives
• On the theory of average case complexity
• Structural complexity of AvgBPP

Cited in

(3)

• Circuit lower bounds for average-case MA
• Structural complexity of AvgBPP
• Structure in average case complexity

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