Complexity Theory: A Modern Approach
A draft of a textbook on computational complexity theory. Covers basic complexity classes, lowerbounds for concrete computational models, and some advanced topics.
Tag(s): Theory of Computation
Publication date: 20 Apr 2009
ISBN-10: 0521424267
ISBN-13: 9780521424264
Paperback: 594 pages
Views: 25,802
Complexity Theory: A Modern Approach
Sanjeev Arora wrote:Not to be reproduced or distributed without the author's permission.
About The Author(s)
Sanjeev Arora is Charles C. Fitzmorris Professor of Computer Science at Princeton University. His research area is Theoretical Computer Science. He has worked on Computational Complexity, Probabilistically Checkable Proofs (PCPs), computing approximate solutions to NP-hard problems, geometric embedding of metric spaces, unique games conjecture, complexity of financial derivatives, and provable bounds for Machine Learning.
Sanjeev Arora is Charles C. Fitzmorris Professor of Computer Science at Princeton University. His research area is Theoretical Computer Science. He has worked on Computational Complexity, Probabilistically Checkable Proofs (PCPs), computing approximate solutions to NP-hard problems, geometric embedding of metric spaces, unique games conjecture, complexity of financial derivatives, and provable bounds for Machine Learning.
Boaz Barak is the Gordon McKay professor of Computer Science at Harvard University's John A. Paulson School of Engineering and Applied Sciences. Until January 2016 he will also continue in his position as a principal researcher in Microsoft Research New England where he has worked since 2010. His research interests include all areas of theoretical computer science, particularly cryptography and computational complexity.
Boaz Barak is the Gordon McKay professor of Computer Science at Harvard University's John A. Paulson School of Engineering and Applied Sciences. Until January 2016 he will also continue in his position as a principal researcher in Microsoft Research New England where he has worked since 2010. His research interests include all areas of theoretical computer science, particularly cryptography and computational complexity.