Average-Case Complexity
From MaRDI portal
Publication:3522267
DOI10.1561/0400000004zbMath1143.68401OpenAlexW2156369551MaRDI QIDQ3522267
Luca Trevisan, Andrej Bogdanov
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
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (13)
Generic case complexity of the graph isomorphism problem ⋮ Computing equilibria: a computational complexity perspective ⋮ Encoding invariance in average case complexity ⋮ Optimal heuristic algorithms for the image of an injective function ⋮ Unnamed Item ⋮ Constructing concrete hard instances of the maximum independent set problem ⋮ On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography ⋮ An infinitely-often one-way function based on an average-case assumption ⋮ On complete one-way functions ⋮ Average Case Complexity, Revisited ⋮ Structural Complexity of AvgBPP ⋮ From Graph Theory to Network Science: The Natural Emergence of Hyperbolicity (Tutorial) ⋮ Bayesian Decision Making in Groups is Hard
This page was built for publication: Average-Case Complexity
