Computational Complexity by Sanjeev Arora, Boaz Barak

This beginning graduate textbook describes both recent achievements and classical results of computational complexity theory. Requiring essentially no background apart …