Thomas Watson is Associate Professor of Computer Science at the University of Memphis. He received his Ph.D. from the University of California, Berkeley. His research spans many areas of computational complexity and has been supported by an NSF CAREER award.

• Prologue; Part I. Time and Space: 1. Efficient computation; 2. Time complexity; 3. Space complexity; 4. A time-space lower bound; 5. Nonuniformity; 6. Parallelism; Part II. Randomness: 7. Randomized computation; 8. Hashing; 9. Error correcting codes; 10. Heuristics; 11. Pseudorandomness; Part III. Scope of Complexity: 12. Cryptography; 13. Learning; 14. Optimization; 15. Verification; Part IV. Concrete Models: 16. Decision trees and branching programs; 17. Communication protocols; 18. Circuits and formulas; Epilogue; Appendix. Discrete math background; References; Index.

'Watson's Complexity in Computer Science is a comprehensive introduction to computational complexity. It is especially well suited for students new to the area who want to learn both the foundations of the field and its connections to other areas of computer science, such as cryptography and learning theory. Its breadth and level of detail make it an invaluable resource for students.' Shachar Lovett, University of California, San Diego