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