**Computational Complexity: A Conceptual Perspective**

by Oded Goldreich

**Publisher**: Cambridge University Press 2008**ISBN/ASIN**: 052188473X**ISBN-13**: 9780521884730**Number of pages**: 632

**Description**:

This book offers a comprehensive perspective to modern topics in complexity theory, which is a central field of the theoretical foundations of computer science. It addresses the looming question of what can be achieved within a limited amount of time with or without other limited natural computational resources. The book can be used as an introduction for advanced undergraduate and graduate students as either a textbook or for self-study, or to experts, since it provides expositions of the various sub-areas of complexity theory such as hardness amplification, pseudorandomness and probabilistic proof systems.

Download or read it online for free here:

**Download link**

(1.4MB, PS)

## Similar books

**Introduction to Computational Complexity**

by

**Martin Tompa**

Lecture notes for a graduate course on computational complexity taught at the University of Washington. Alternating Turing machines are introduced very early, and deterministic and nondeterministic Turing machines treated as special cases.

(

**9557**views)

**Introduction to Complexity Theory**

by

**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.

(

**10642**views)

**Think Complexity: Complexity Science and Computational Modeling**

by

**Allen B. Downey**-

**Green Tea Press**

This book is about complexity science, data structures and algorithms, intermediate programming in Python, and the philosophy of science. The book focuses on discrete models, which include graphs, cellular automata, and agent-based models.

(

**9228**views)

**Algorithms and Complexity**

by

**Herbert S. Wilf**-

**AK Peters, Ltd.**

An introductory textbook on the design and analysis of algorithms. Recursive algorithms are illustrated by Quicksort, FFT, and fast matrix multiplications. Algorithms in number theory are discussed with some applications to public key encryption.

(

**20966**views)