Foundations and Trends® in Theoretical Computer Science
AVERAGE-CASE COMPLEXITY
by Andrej Bogdanov (Rutgers University, USA) & Luca Trevisan (University of California, Berkeley, USA)
Average-Case Complexity is a thorough survey of the average-case complexity of problems in NP. The study of the average-case complexity of intractable problems began in the 1970s, motivated by two distinct applications: the developments of the foundations of cryptography and the search for methods to “cope” with the intractability of NP-hard problems. This survey looks at both, and generally examines the current state of knowledge on average-case complexity.
Average-Case Complexity is intended for scholars and graduate students in the field of theoretical computer science. The reader will also discover a number of results, insights, and proof techniques whose usefulness goes beyond the study of average-case complexity.
Published by Now Publishers and marketed by World Scientific
Contents:
- Abstract
- Introduction
- Definitions of “Efficient on Average”
-
A Complete Problem for Computable Ensembles
- Decision versus Search and One-Way Functions
- Samplable Ensembles
- Hardness Amplification
- Worst-Case versus Average-Case and Cryptography
- Other Topics
- Acknowledgements
- References
Readership: Scholarly and professionals.
| 120pp |
Pub. date: Oct 2006 |
|
