Complexity of distributions and average-case hardness

DOI10.4230/LIPICS.ISAAC.2016.38MaRDI QIDQ4636521zbMATH OpenOpenAlexFDO

Authors Dmitry Itsykson, Alexander Knop, Dmitry Sokolov

Publication date 19 April 2018

Full work available at URL https://doi.org/10.4230/LIPIcs.ISAAC.2016.38

zbMATH Keywords

average-case complexitydiagonalizationhierarchy theoremsampling distributions

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Recommendations

• On the theory of average case complexity
• All natural NP-complete problems have average-case complete versions
• scientific article; zbMATH DE number 512870
• Complete distributional problems, hard languages, and resource-bounded measure
• scientific article; zbMATH DE number 5081744

Cited in

(14)

• Complete distributional problems, hard languages, and resource-bounded measure
• The value of help bits in randomized and average-case complexity
• On the hardness of finding subsets with equal average
• An encoding invariant version of polynomial time computable distributions
• Worst-Case Vs. Algorithmic Average-Case Complexity in the Polynomial-Time Hierarchy
• The Complexity of Malign Measures
• On Average Case Complexity of SAT for Symmetric Distribution
• scientific article; zbMATH DE number 1114051 (Why is no real title available?)
• Malign distributions for average case circuit complexity
• The Complexity and Distribution of Hard Problems
• Complete problems with L-samplable distributions
• Distributionally hard languages
• Robustness of average-case meta-complexity via pseudorandomness
• Complete problems with L-samplable distributions

This page was built for publication: Complexity of distributions and average-case hardness

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