Complexity Theory: A Modern Approach
by Sanjeev Arora, Boaz Barak
Publisher: Cambridge University Press 2008
ISBN/ASIN: 0521424267
ISBN-13: 9780521424264
Number of pages: 489
Description:
This book aims to describe such recent achievements of complexity theory in the context of the classical results. It is intended to be a text and as well as a reference for self-study. This means it must simultaneously cater to many audiences, and it is carefully designed with that goal. The book will explain the context in which a certain notion is useful, and why things are defined in a certain way. Examples and solved exercises accompany key definitions. This book assumes essentially no computational background (though a slight exposure to computing may help) and very little mathematical background apart from the ability to understand proofs and some elementary probability on finite sample spaces. A typical undergraduate course on "Discrete Math" taught in many math and CS departments should suffice (together with the Appendix).
Download or read it online for free here:
Download link
(4.4MB, PDF)
Similar books
Foundations of Cryptographyby Oded Goldreich - Cambridge University Press
The book gives the mathematical underpinnings for cryptography; this includes one-way functions, pseudorandom generators, and zero-knowledge proofs. Throughout, definitions are complete and detailed; proofs are rigorous and given in full.
(16783 views)
Measure-Preserving Systemsby Karl Petersen - University of North Carolina
These notes provide an introduction to the subject of measure-preserving dynamical systems, discussing the dynamical viewpoint; how and from where measure-preserving systems arise; the construction of measures and invariant measures; etc.
(10766 views)
Introduction to Complexity Theoryby Oded Goldreich
Complexity theory is the study of the intrinsic complexity of computational tasks. The book is aimed at exposing the students to the basic results and research directions in the field. The focus was on concepts, complex technical proofs were avoided.
(10738 views)
Lecture Notes on Computational Complexityby Luca Trevisan
Notes from a graduate courses on Computational Complexity. The first 15 lectures cover fundamentals, the remaining is advanced material: Hastad's optimal inapproximability results, lower bounds for parity in bounded depth-circuits, and more.
(15091 views)