Complexity Theory related surveys

Some complexity related survey-ish papers:
A CACM article from September 2009 titled "The status of the P versus NP problem" available here.

Mentioned in the above survey, two more interesting papers:

• an article by Scott Aaronson on the independence of the P vs. NP question
• a paper by Impagliazzo giving a personal view on the average case complexity

I did not have enough time to read more of the cited works in the CACM article, but I'll add more as I have time to read it.

Some results in quantum computing

Just some points to (rather) recent results in complexity theory with regard to quantum computing:

• Quantum Interative Proofs equals Polynomial Space class: QIP = PSPACE
  
• On the relation of the BQP class to the PH class; furthermore a separating decision problem would follow from the Generalized Linial-Nisan Conjecture: BQP vs PH