From ResearchWiki

Contents 1 Resources 2 Course Outline 3 Surprising things 4 People/Research Groups 5 Books 6 Conferences 7 Blogs 8 Misc Links 9 Non-trivial Trivia (.....pardon the oxymoron)

Resources

• Complexity Theory, by Arora and Barak
• The Complexity Zoo (invaluable reference page for definitions of classes)

Course Outline

• Why P-time (TMs, invariance of machine models, basic hierarchy theorems) (Chapter 1)
• Trust but verify (nondeterminism): non-d space. Savitch's theorem, non-d time, Cook's theorem, Reductions
• Let's play a game: PSPACE, QBF, ptime-hierarchy in terms of alternating TMs ?
• Can someone please prove a lower bound ? Circuits, why non-uniformity is needed, lower bounds for circuits, relation to parallel computing
• Should I toss a coin ? randomness, BPP, RP, BPP and circuit classes; hardness vs randomness
• Let's talk ! Interaction, IP, PSPACE, PCPs, communication complexity. Link to approximation hardness.
• Wave/particle ? rudimentary quantum complexity: BQP vs NP.
• Computation and Logic: Fagin's theorem

Things deliberately omitted because the audience is not specialist theory: oracles, natural proofs, sparseness, details of MA/AM/MIP=NEXP, Toda's theorem

For more, see Bill Gasarch's post and the comments.

Surprising things

• complementing affects time (we don't know that NP = co-NP) but not space (NSPACE = co-NSPACE!)
• non-determinism affects time (P ? NP) but not space (PSPACE = NPSPACE)

People/Research Groups

• Theory@CMU
  
• Scott Aaronson
  
• William Gasarch
  

Books

• Complexity Theory: A Modern Approach by Arora and Barak
  
• Computational Complexity by Christos Papadimitriou
  
• Theory: Exploring the Limits of Efficient Algorithms by Ingo Wegener
  
• Computers and Intractability: A Guide to the Theory of NP-Completeness by Garey Johnson
  
• Elements of the Theory of Computation by Lewis Papadimitriou
  
• Automata and Computability by Kozen
  
• This book by Kozen is more advanced, but is nicely structured in bite-sized chapters.
• Introduction to the Theory of Computation by Michael Sipser
  
• An online book by Elaine Rich
  

Conferences

• IEEE Conference on Computational Complexity
  
• Electronic Colloquium on Computational Complexity

Blogs

• by William Gasarch
  
• In Theory, by Luca Trevisan.
• by Kurt Van Etten

Misc Links

• What is Theoretical Computer Science? by Sanjeev Arora
• A short history of computational complexity
  
• A graphical taxonomy of complexity classes
  
• The Theoretical Computer Science (TCS) Advocacy Wiki
  
• BEATCS
  
• Computational Complexity of Games and Puzzles
• A compendium of NP optimization problems maintained by Pierluigi Crescenzi and Viggo Kann

Non-trivial Trivia (.....pardon the oxymoron)

1. Did you know how many complexity classes are there ? guess.....guess more.....here's the answer
2. Did ever you ever think that P and NP weren't "quite" properly named ? Well, here's someone who thinks so !!
3. One may draw inspiration from the size of this group !! Theoreticians aren't that scary creatures afterall :)
4. The myriad complexity classes offer a potential research problem to NLP researchers
5. .........more to follow
0*. And last but not the least here's a reason (courtesy Suresh) as to why we should keep this informal discussion group going
[*] - numbered zero because I think that it ought to be the first and most important reason but anyhow decided to put it at the end