Arora on Computational Complexity

Sanjeev Arora is writing a new book on computational complexity, and he’s posting the draft chapters online. Since the standard textbook on the subject, Papadimitriou’s Computational Complexity, is from 1993, a more-recent take on the subject is much appreciated.

I’m a total amateur in the subject, but my impression looking at the notes is that the big difference between 1993 and now is that in 1993 researchers were already beginning to suspect that the best idea in years for settling P versus NP (circuit complexity) wasn’t going to work, and now they’re pretty sure it won’t work.

In the introduction, Arora provides a more succinct summary of the post-1993 work than I possibly could:

The list of surprising and fundamental results proved in the 1990s alone could fill a book: these include new probabilistic definitions of classical complexity classes ( IP = PSPACE and the PCP Theorems) and their implications for the field of approximation algorithms; Shor’s algorithm to factor integers using a quantum computer; an understanding of why current approaches to the famous P versus NP will not be successful; a theory of derandomization and pseudorandomness based upon computational hardness; and beautiful constructions of pseudorandom objects such as extractors and expanders.

We’ve previously linked to some expository material on expanders.

Via Scott Aaronson.

One thought on “Arora on Computational Complexity

  1. “If you’re willing to invest the effort, you’ll find The Road to Reality so excellent that it “cancels out” Shadows of the Mind, like an electron annihilating its positronic companion.”

    This is quite possibly my favorite sentence of 2006.

Comments are closed.