TY  - GEN
AU  - Arora,Sanjeev
AU  - Barak,Boaz
TI  - Computational complexity: a modern approach
SN  - 9780521424264 (Cloth)
U1  - 511.352 
PY  - 2009///
CY  - Cambridge, New York
PB  - Cambridge University Press
KW  - Computational complexity
N1  - Contine bibliogr. si index; 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
ER  -