Computational complexity: a modern approach Sanjeev Arora, Boaz Barak
Publication details: Cambridge New York Cambridge University Press 2009Description: xxiv, 579 p ill 26 cmISBN:- 9780521424264 (Cloth)
- 0521424267 (Cloth)
- 511.352
Item type | Current library | Call number | Copy number | Status | Date due | Barcode | |
---|---|---|---|---|---|---|---|
Carti | IMAR | II 36900 (Browse shelf(Opens below)) | 1 | Checked out | 04/18/2025 | 0029856 |
Browsing IMAR shelves Close shelf browser (Hides shelf browser)
eng
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
There are no comments on this title.