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
Algorithmic Randomness and Complexityby R. G. Downey, D. R. Hirschfeldt - Springer
Computability and complexity theory are two central areas of research in theoretical computer science. This book provides a systematic, technical development of algorithmic randomness and complexity for scientists from diverse fields.
(10106 views)
Complexity and Computationby Allen Downey - Green Tea Press
This book is about data structures and algorithms, intermediate programming in Python, complexity science and the philosophy of science. The book covers Graphs, Analysis of algorithms, Scale-free networks, Cellular Automata, Agent-based models, etc.
(15624 views)
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)
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.
(8917 views)