Average-case complexity

Author(s)

• Bogdanov, Andrej
• Trevisan, Luca

Bibliographic Information

Average-case complexity

Andrej Bogdanov, Luca Trevisan

（Foundations and trends in theoretical computer science, 2:1）

now Publishers, c2006

Other Title

Average case complexity

Note

"The preferred citation for this publication is ... Foundation and Trends [R] in Theoretical Computer Science, vol 2, no 1, pp 1-106, 2006"-T. p. verso

Bibliography: p. 107-111

Description and Table of Contents

Description

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. The book 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.

Table of Contents

• 1. Introduction
• 2. Definitions of "Efficient on Average"
• 3. A Complete Problem for Computable Ensembles
• 4. Decision versus Search and One-Way Functions
• 5. Samplable Ensembles
• 6. Hardness Amplification
• 7. Worst-Case versus Average-Case and

by "Nielsen BookData"

Details

• NCID: BA84343499
• ISBN:
  • 1933019492
• LCCN: 2006935853
• Country Code: us
• Title Language Code: eng
• Text Language Code: eng
• Place of Publication: Hanover, MA
• Pages/Volumes: ix, 111 p.
• Size: 24 cm
• Parent Bibliography ID:
  • BA81053856