Description
Table of Contents Computational Complexity : A Modern Approach by Arora, Sanjeev; Barak, Boaz Terms of Use Part I Basic Complexity Classes 1 The computational model - and why it doesn't matter 2 NP and NP completeness 3 Diagonalization 4 Space complexity 5 The polynomial hierarchy and alternations 6 Boolean circuits 7 Randomized computation 8 Interactive proofs 9 Cryptography 10 Quantum computation 11 PCP theorem and hardness of approximation: an introduction Part II Lower Bounds for Concrete Computational Models 12 Decision trees 13 Communication complexity 14 Circuit lower bounds 15 Proof complexity 16 Algebraic computation models Part III Advanced Topics 17 Complexity of counting 18 Average case complexity: Levin's theory 19 Hardness amplification and error correcting codes 20 Derandomization 21 Pseudorandom constructions: expanders and extractors 22 Proofs of PCP theorems and the Fourier transform technique 23 Why are circuit lower bounds so difficult? Appendix A mathematical background Copyright ® 2011 R.R. Bowker LLC. All Rights Reserved. Summary Computational Complexity : A Modern Approach by Arora, Sanjeev; Barak, Boaz Terms of use This beginning graduate textbook describes both recent achievements and classical results of computational complexity theory. Requiring essentially no background apart from mathematical maturity, the book can be used as a reference for self-study for anyone interested in complexity, including physicists, mathematicians, and other scientists, as well as a textbook for a variety of courses and seminars. More than 300 exercises are included with a selected hint set. Copyright ® 2011 R.R. Bowker LLC. All Rights Reserved.
