Algorithmic Randomness and Complexity
by R. G. Downey, D. R. Hirschfeldt
Publisher: Springer 2010
ISBN/ASIN: 0387955674
ISBN-13: 9780387955674
Number of pages: 629
Description:
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.
Download or read it online for free here:
Download link
(4MB, PDF)
Similar books

- 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.
(8065 views)

by Oded Goldreich - Cambridge University Press
The main focus of the current book is on the P-vs-NP Question and the theory of NP-completeness. Additional topics that are covered include the treatment of the general notion of a reduction between computational problems.
(8574 views)

by 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.
(8642 views)

by Sanjeev Arora, Boaz Barak - Cambridge University Press
The book provides an introduction to basic complexity classes, lower bounds on resources required to solve tasks on concrete models such as decision trees or circuits, derandomization and pseudorandomness, proof complexity, quantum computing, etc.
(16559 views)