In complexity two of the unique games papers I mentioned on Monday will be at FOCS. Some other interesting looking complexity papers:
- Mark Braverman, On the Complexity of Real Functions.
- O'Donnell, Saks, Schramm and Servedio, "Every decision tree has an influential variable". I can't find the paper online but here is a talk abstract. Update 6/30: Paper is now available.
- Ran Raz, Quantum Information and the PCP Theorem where he shows, among other results, that every language has a quantum interactive proofs with quantum advice.