On the theory of average case complexity

DOI10.1016/0022-0000(92)90019-FzbMath0762.68027OpenAlexW2173249896MaRDI QIDQ1190984

Michel Luby, Benny Chor, Shai Ben-David, Oded Goldreich

Publication date: 27 September 1992

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(92)90019-f

zbMATH Keywords

average case complexitydistributional decision problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

Complete on average Boolean satisfiability, Computational depth: Concept and applications, Secret sharing based on a hard-on-average problem, The complexity of generating test instances, The Journey from NP to TFNP Hardness, Some properties of sets tractable under every polynomial-time computable distribution, An average complexity measure that yields tight hierarchies, Batch Diffie-Hellman key agreement systems, Is Valiant-Vazirani's isolation probability improvable?, Average-case intractability vs. worst-case intractability, The query complexity of witness finding, Encoding invariance in average case complexity, Sets computable in polynomial time on average, Rankable distributions do not provide harder instances than uniform distributions, Reductions and convergence rates of average time, The computational complexity of generating random fractals, Structural complexity of AvgBPP, An approach to estimating the average-case complexity of postoptimality analysis of discrete optimization problems, Relations between average-case and worst-case complexity, An infinitely-often one-way function based on an average-case assumption, Notes on Levin’s Theory of Average-Case Complexity, Average Case Complexity, Revisited, Learning with restricted focus of attention, Structural Complexity of AvgBPP, Derandomizing Isolation in Space-Bounded Settings, Unnamed Item, Complete distributional problems, hard languages, and resource-bounded measure, Polynomial time samplable distributions, Malign distributions for average case circuit complexity., Complete problems with L-samplable distributions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• NP is as easy as detecting unique solutions
• One way functions and pseudorandom generators
• On uniform circuit complexity
• Universal classes of hash functions
• Time polynomial in input or output
• Average Case Complete Problems
• On the Structure of Polynomial Time Reducibility
• The NP-completeness column: An ongoing guide