Average-Case Complexity (Foundations and Trends(R) in Theoretical Computer Science)

✍ Scribed by Andrej Bogdanov, Luca Trevisan

Publisher: Now Publishers Inc
Year: 2006
Tongue: English
Leaves: 122
Series: Foundations and Trends R in Theoretical Computer Science
Category: Library

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

Lower Bounds in Communication Complexity

📁 Lower Bounds in Communication Complexity (Foundations and Trends in Theoretical Computer Science)

✍ Troy Lee, Adi Shraibman 📂 Library 📅 2009 🏛 Now Publishers Inc 🌐 English

Pairwise Independence and Derandomizatio

📁 Pairwise Independence and Derandomization (Foundations and Trends(R) in Theoretical Computer Science)

✍ Michael Luby, Avi Wigderson 📂 Library 📅 2006 🏛 Now Publishers Inc 🌐 English

Complexity Lower Bounds using Linear Alg

📁 Complexity Lower Bounds using Linear Algebra (Foundations and Trends in Theoretical Computer Science)

✍ Satyanarayana V. Lokam 📂 Library 📅 2009 🏛 Now Publishers Inc 🌐 English

ALGORITHMIC RESULTS IN LIST DECODING (Fo

📁 ALGORITHMIC RESULTS IN LIST DECODING (Foundations and Trends(R) in Theoretical Computer Science)

✍ Venkatesan Guruswami 📂 Library 📅 2007 🏛 Now Publishers Inc 🌐 English

Algorithmic Results in List Decoding introduces and motivates the problem of list decoding, and discusses the central algorithmic results of the subject, culminating with the recent results on achieving "list decoding capacity." The main technical focus is on giving a complete presentation of the re

Arithmetic Circuits (Foundations and Tre

📁 Arithmetic Circuits (Foundations and Trends in Theoretical Computer Science)

✍ Amir Shpilka, Amir Yehudayoff 📂 Library 📅 2010 🏛 Now Publishers Inc 🌐 English

Algorithms and Data Structures for Exter

📁 Algorithms and Data Structures for External Memory (Foundations and Trends(R) in Theoretical Computer Science)

✍ Jeffrey Scott Vitter 📂 Library 📅 2008 🏛 Now Publishers Inc 🌐 English

Data sets in large applications are often too massive to fit completely inside the computer's internal memory. The resulting input/output communication (or I/O) between fast internal memory and slower external memory (such as disks) can be a major performance bottleneck. Algorithms and Data Structur