TCS Reading List / Resources

The following books/resources could be useful to students interested in theoretical Ccomputer Science research.

Undergraduate texts:

• Algorithms: Introduction to Algorithms / Cormen, leiserson, Rivest, and Stein
• Computability, NP-completeness: Introduction to the Theory of Computing / Sipser
• Discrete Math: Some lecture notes:

 * http://www.theory.lcs.mit.edu/~e_lehman/mathcs.pdf
 * http://www.cs.berkeley.edu/~vazirani/f06cs70.html 
 * http://inst.eecs.berkeley.edu/~cs70/sp07/

Some graduate-level texts:

• The Probabilistic Method / Alon & Sipser
• Extremal Combinatorics / Jukna
• Computational Introduction to Number Theory and Algebra / Shoup http://shoup.net/ntb/
• Computational Complexity: A Modern Approach / Arora & Barak http://www.cs.princeton.edu/theory/complexity/

Graduate texts on specialized topics:

• Additive Combinatorics / Tao & Vu (Fall 2007 will have a special term on this topic in the IAS)
• Expander Graphs / Hoory, Linial, Wigderson http://www.math.ias.edu/~avi/BOOKS/expanderbookr1.pdf
• Coding Theory / Sudan: http://theory.csail.mit.edu/~madhu/FT04/
• Algebraic Methods in Computation / Sudan : http://theory.csail.mit.edu/~madhu/FT05/
• Analysis of Boolean Functions / O'Donnell : http://www.cs.cmu.edu/%7Eodonnell/boolean-analysis/

Popular Science books

• Computers Ltd.: What they really can't do / David Harel
• Mathematics: A very short introduction / Timothy Gowers

Online resources.

In addition to the sites below, you can find a lot of useful information - papers, lecture notes, and surveys - on the web sites of TCS researchers (easily reachable via Google).

• ECCC - Electronic Colloquium on Computational Complexity
• Theory of Computing Journal
• Foundations and Trends in Theoretical Computer Science
• Cryptology Eprint Archive
• Theory Matters Wiki