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