Theoretical computer science books

Last update: Thu Mar 2 10:57:32 EST 2017


Luc's library has now opened its web doors to all McGill University students. The library is in fact my office (room 300N, McConnell Engineering Building), and the books are a subset of my private collection. Any McGill student may borrow any book at any time!



ACM

Proceedings of the 26th Annual ACM Symposium on the Theory of Computing [Google]
ACM Press, New York, 1994.

A. V. Aho
J. D. Ullman

Foundations of Computer Science [Google]
W.H. Freeman, New York, 1992.

A. V. Aho
J. D. Ullman

Foundations of Computer Science (C edition) [Google]
W.H. Freeman, New York, 1995.

Sanjeev Arora
Boaz Barak

Computational Complexity: A Modern Approach [Google]
Cambridge University Press, New York, 2009.

M.J. Atallah (ed)

Algorithms and Theory of Computation Handbook [Google]
CRC Press, Boca Raton, FL, 1999.

M.J. Atallah (ed)

Algorithms and Theory of Computation Handbook [Google]
CRC Press, Boca Raton, FL, 1999.

G. Ausiello
M. Dezani-Ciancaglini
S. Ronchi della Rocca (eds)

Automata, Languages and Programming: 16th ICALP [Google]
Springer-Verlag, Berlin, 1989.

J.L. Balcázar
J. D\'iaz
J. Gabarró

Structural Complexity II [Google]
Springer-Verlag, Berlin, 1990.

J.L. Balcázar
J. D\'iaz
J. Gabarró

Structural Complexity I (2nd ed) [Google]
Springer-Verlag, Berlin, 1995.

Andrej Bogdanov
Luca Trevisan

Average-Case Complexity [Google]
Now Publishers, Hanover, MA, 2006.

R.B. Boppana
J.F. Lynch (eds)

Logic and Random Structures [Google]
The American Mathematical Society, Providence, RI, 1997.

P. Bürgisser
M. Clausen
M.A. Shokrollahi

Algebraic Complexity Theory [Google]
Springer Verlag, 1996.

Cristian Calude

Information and Randomness. An Algorithmic Perspective [Google]
Springer-Verlag, Berlin, 1994.

J. Carroll
D. Long

Theory of Finite Automata [Google]
Prentice-Hall, Englewood Cliffs, NJ, 1989.

Gregory J. Chaitin

Exploring Randomness [Google]
Springer-Verlag, London, 2001.

E.G. Coffman
J.K. Lenstra
A.H.G. Rinnooy Kan (eds)

Handbooks in Operations Research and Management Science Volume 3 Computing [Google]
North-Holland, Amsterdam, 1992.

Dingzhu Du
Xiaodong Hu

Steiner Tree Problems in Computer Communication Networks [Google]
World Scientific, 2009.

Dingzhu Du
Xiaodong Hu

Steiner Tree Problems in Computer Communication Networks [Google]
World Scientific, 2009.

R. Durbin
S. Eddy
A. Krogh
G. Mitchison

Biological Sequence Analysis Probabilistic Models of Proteins and Nucleic Acids [Google]
Cambridge University Press, Cambridge, UK, 1998.

Jörg Flum
Martin Grohe

Parametrized Complexity Theory [Google]
Springer-Verlag, Berlin, 2006.

M. R. Garey
D. S. Johnson

Computers and Intractability: A Guide to the Theory of $NP$-Completeness [Google]
W. H. Freeman, New York, 1979.

Moritz Hardt

Testing Polynomial Identities with Fewer Random Bits: Can You Fool a Polynomial without Rolling Dice? [Google]
VDM Verlag Dr. Müller, Saarbrücken, 2008.

M.A. Harrison

Introduction to Formal Language Theory [Google]
Addison-Wesley, Reading, MA, 1978.

Juraj Hromkovic

Design and Analysis of Randomized Algorithms [Google]
Springer-Verlag, Berlin, 2005.

Eyal Hushilevitz
Noam Nisan

Communication Complexity [Google]
Cambridge University Press, Cambridge, 1997.

J. Kilian

Uses of Randomness in Algorithms and Protocols [Google]
MIT Press, Cambridge, MA, 1991.

Donald E. Knuth

The Art of Computer Programming Volume 4 Introduction to Combinatorial Algorithms and Boolean Functions [Google]
Pearson Education Inc, Upper Saddle River, NJ, 2008.

W. Kuich (ed)

Automata, Languages and Programming: 19th ICALP [Google]
Springer-Verlag, Berlin, 1989.

H.R. Lewis
C.H. Papadimitriou

Elements of the Theory of Computation [Google]
Prentice-Hall, Englewood Cliffs, NJ, 1981.

Ming Li
Paul Vitányi

An Introduction to Kolmogorov Complexity and its Applications [Google]
Springer Verlag, 1993.

Ming Li
Paul Vitányi

An Introduction to Kolmogorov Complexity and its Applications (Revised and expanded second edition) [Google]
Springer-Verlag, New York, 1997.

M. Luby

Pseudorandomness and Cryptographic Applications [Google]
Princeton University Press, Princeton, NJ, 1996.

C.L. Lucchesi
A.V. Moura (eds)

LATIN'98: Theoretical Informatics [Google]
Springer-Verlag, Berlin, 1998.

Ernst W. Mayr
Hans Jürgen Prömel
Angelika Steger (eds)

Lectures on Proof Verification and Approximation Algorithms [Google]
Springer-Verlag, Berlin, 1998.

R. McNaughton

Elementary Computability, Formal Languages and Automata [Google]
Prentice-Hall, Englewood Cliffs, NJ, 1982.

Ravi Montenegro
Prasad Tetali

Mathematical Aspects of Mixing Times in Markov Chains [Google]
Now Publishers, Hanover, MA, 2006.

Noam Nisan
T. Roughgarden
E. Tardos
V.J. Vazirani (eds.)

Algorithmic Game Theory [Google]
Cambridge University Press, Cambridge, 2007.

Noam Nisan
T. Roughgarden
E. Tardos
V.J. Vazirani (eds.)

Algorithmic Game Theory [Google]
Cambridge University Press, Cambridge, 2007.

Ryan O'Donnell

Analysis of Boolean Functions [Google]
Cambridge University Press, New York, 2014.

C.H. Papadimitriou

Computational Complexity [Google]
Addison-Wesley, Reading, MA, 1994.

Sanguthevar Rajasekaran
Panos M. Pardalos
John H. Reif
José Rolim (eds)

Handbook of Randomized Computing Volume II [Google]
Kluwer Academic Publishers, Dordrecht, The Netherlands, 2001.

Sanguthevar Rajasekaran
Panos M. Pardalos
John H. Reif
José Rolim (eds)

Handbook of Randomized Computing Volume I [Google]
Kluwer Academic Publishers, Dordrecht, The Netherlands, 2001.

John E. Savage

Models of Computation: Exploring the Power of Computing [Google]
Addison-Wesley, Reading, MA, 1998.

U. Schöning
R. Pruim

Gems of Theoretical Computer Science [Google]
Springer-Verlag, New York, 1998.

J. Setubal
J. Meidanis

Introduction to Computational Molecular Biology [Google]
PWS Publishing Company, Boston, 1997.

M. Sipser

Introduction to the Theory of Computation [Google]
PWS Publishers, Boston, 1996.

M. Sipser

Introduction to the Theory of Computation Second Edition [Google]
Thomson, Boston, 2006.

J. Van Leeuwen (ed)

Handbook of Theoretical Computer Science, volume A: Algorithms and Complexity [Google]
Elsevier Science and MIT Press, Cambridge, MA, 1990.

Vijay V. Vazirani

Approximation Algorithms [Google]
Springer-Verlag, Heidelberg, 2001.

Vijay V. Vazirani

Approximation Algorithms [Google]
Springer-Verlag, Heidelberg, 2001.

Osamu Watanabe
Thomas Zeugmann (eds)

Stochastic Algorithms: Foundations and Applications [Google]
Springer, 2009.

I. Wegener

Branching Programs and Binary Decision Diagrams [Google]
SIAM, Philadelphia, 2000.

Ingo Wegener

Complexity Theory [Google]
Springer-Verlag, Berlin, 2005.

Sidney Yakowitz
Ferenc Szidarovsky

An Introduction to Numerical Computation Second Edition [Google]
Macmillan, New York, 1989.



Contact

Luc Devroye
School of Computer Science
McGill University
Montreal, Canada H3A 2K6
lucdevroye@gmail.com
http://cg.scs.carleton.ca/~luc