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
Parallel Complexity Theoryby Ian Parberry - Prentice Hall
The rapid growth of parallel complexity theory has led to a proliferation of parallel machine models. This book presents a unified theory of parallel computation based on a network model. It is the first such synthesis in book form.
(6079 views)
Communication Complexity (for Algorithm Designers)by Tim Roughgarden - Stanford University
The two biggest goals of the course are: 1. Learn several canonical problems that have proved the most useful for proving lower bounds; 2. Learn how to reduce lower bounds for fundamental algorithmic problems to communication complexity lower bounds.
(2522 views)
Computability and Complexity- Wikibooks
This book is intended as an introductory textbook in Computability Theory and Complexity Theory, with an emphasis on Formal Languages. Its target audience is CS and Math students with some background in programming and data structures.
(5636 views)
Specifying Systemsby Leslie Lamport - Addison-Wesley Professional
This book shows how to write unambiguous specifications of complex computer systems. It provides a complete reference manual for the TLA+, the language developed by the author for writing simple and elegant specifications of algorithms and protocols.
(10944 views)