The following list has been suggested by Rod Downey for those looking for general background on complexity theory.

Initial segments of:

• Computers and Intractability by M. Garey and D. Johnson (Freeman Press, 1979)
• Complexity: Knots, Colouring and Counting by D. Welsh (London Math Soc. Lecture Notes 186, Cambridge University Press, 1993)

Dipping through one of the following:

• Automata and Computability or The Design and Analysis of Algorithms by D. Kozen (Springer-Verlag, 1997 and 1991)
• The Theory of Computation by B. Moret (Addison-Wesley, 1998)

The following reading lists have been suggested by the speakers.

Eric Allender (Basic Complexity)

Standard texts:

• Computers and Intractability
  M. Garey and D. Johnson
  Freeman Press
  
• Introduction to Automata Theory, Languages and Computation
  J. Hopcroft and J. Ullman
  Addison-Wesley
  (Chapters 12-13)

Three survey chapters by the speaker:

• (1)"Complexity Classes"
  (2)"Reducibility and Completeness"
  (3) "Other Complexity Classes and Measures"
  by Eric Allender, Michael Loui, Kenneth Regan
  in the CRC Handbook of Algorithms and Theory of Computation
  ed. M. Atallah
  CRC Press
  (Chapters available at www.cs.rutgers.edu/~allender/publications)

Elwyn Berlekamp

• Elwyn Berlekamp, John Conway, & Richard Guy: Winning Ways, (vols I & II)
  Academic Press, 1982
  Especially recommended: Chapters 1,2,3,6.
• Richard Nowakowski, ed: Games of No Chance
  Cambridge U. Press, 1996
  Especially recommended: Pages 365-405
• Elwyn Berlekamp & David Wolfe: Mathematical Go
  AK Peters, Ltd, 1994
  Japanese translation by Yoshigawa published by Toppan

Felipe Cucker (Real Computation)

• Complexity and Real Computation
  L. Blum, F. Cucker, S. Shub, and S. Smale
  Springer-Verlag, 1998

Mike Fellows (Parameterized Complexity, Treewidth and the like)

Survey papers, available at http://www.mcs.vuw.ac.nz/research/maths-pubs.shtml:

• "Parameterized Complexity After (Almost) 10 Years: Review and Open Questions"
  Downey and Fellows
• "Computational Tractability: The View From Mars"
  Downey, Fellows, and Stege
• "Parameterized Complexity: A Framework for Systematically Confronting Computational Intractability"
  Downey, Fellows, and Stege

Monograph:

• Parameterized Complexity
  Downey and Fellows
  Springer, 1999

Lance Fortnow (Kolmogorov Complexity)

• An Introduction to Kolmogorov Complexity and Its Applications by Li and Vitanyi
  Springer-Verlag, 1997.

Cheryl Praeger (Complexity and Computation in Matrix Groups)

• B. Hartley and T. O. Hawkes: Rings, Modules and Linear Algebra
  Chapman and Hall, 1970
  Chapter 11 (Linear transformations, matrices and canonical forms).
• The speaker's survey chapter "Primitive prime divisor elements in finite classical groups"
  in Groups St Andrews 1997 in Bath, II
  Eds. C. M. Campbell, E. F. Robertson, N. Ruskuc and G. C. Smith
  London Math. Soc. Lecture Note Series 261 (1999)
  pp. 605-623.

Dominic Welsh (Enumeration Complexity)

• Computers and Intractability
  Garey and Johnson
  Freeman Press
  especially section 7.3
• Computational Complexity
  Papadimitriou
  Addison-Wesley
  especially chapters 11 and 18
• Complexity: Knots, Colouring and Counting
  Welsh
  London Math Soc. Lecture Notes 186
  Cambridge University Press