Average-Case Complexity

DOI10.1561/0400000004MaRDI QIDQ3522267zbMATH OpenOpenAlexFDO

Authors Andrej Bogdanov, Luca Trevisan

Publication date 1 September 2008

Published in Foundations and Trends® in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1561/0400000004

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)

Recommendations

• scientific article; zbMATH DE number 5081744
• scientific article; zbMATH DE number 1072538
• Average case complexity, revisited
• scientific article; zbMATH DE number 176768
• On the theory of average case complexity
• scientific article; zbMATH DE number 512870
• Structure in average case complexity
• Structural average case complexity
• scientific article; zbMATH DE number 1008511
• Average-case analysis of algorithms using Kolmogorov complexity

Cited in

(22)

• Encoding invariance in average case complexity
• Optimal heuristic algorithms for the image of an injective function
• Generic case complexity of the graph isomorphism problem
• Average case complexity, revisited
• Structural Complexity of AvgBPP
• scientific article; zbMATH DE number 5081744 (Why is no real title available?)
• An infinitely-often one-way function based on an average-case assumption
• Instance complexity
• scientific article; zbMATH DE number 1008511 (Why is no real title available?)
• Bayesian decision making in groups is hard
• From Graph Theory to Network Science: The Natural Emergence of Hyperbolicity (Tutorial)
• Average-Case Completeness in Tag Systems
• Constructing concrete hard instances of the maximum independent set problem
• scientific article; zbMATH DE number 7758317 (Why is no real title available?)
• Searching for (sharp) thresholds in random structures: where are we now?
• Exact search-to-decision reductions for time-bounded Kolmogorov complexity
• Distribution-free proofs of proximity
• A meta-complexity characterization of quantum cryptography
• On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography
• On the efficiency of generic, quantum cryptographic constructions
• On complete one-way functions
• Computing equilibria: a computational complexity perspective

This page was built for publication: Average-Case Complexity

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