complexity2122: Βιβλιογραφία - Υλικό

Βιβλιογραφία - Υλικό - Σύνδεσμοι

Christos Papadimitriou, Computational Complexity, Addison Wesley, 1994
Sanjeev Arora, Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009
Oded Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008
L. Trevisan, Lecture Notes in Computational Complexity, 2002, UC Berkeley.
E. Allender, M. Loui, and K. Regan, Three chapters for the CRC Handbook on Algorithms and Theory of Computation (M.J. Atallah, ed.), (Boca Raton: CRC Press, 1998).
Chapter 27: Complexity Classes
Chapter 28: Reducibility and Completeness
Chapter 29: Other Complexity Classes and Measures
Johan Håstad, Lecture Notes on Complexity Theory, 2009

PCP and Hardness of Approximation, Berkeley, Spring 2006 (Luca Trevisan)
Computational Complexity, Berkeley, Spring 2008 (Luca Trevisan)
Computational Complexity, Princeton, Spring 2007 (Boaz Barak)
Computational Complexity, Princeton, Spring 2001 (Sanjeev Arora)
Computational Complexity, Princeton, Spring 2003 (Sanjeev Arora)
Advanced Complexity Theory, MIT, Spring 2007 (Madhu Sudan)
Complexity of Computation, Rutgers University, Spring 2007 (Eric Allender)
Introduction to Computational Complexity, Brown University, Spring 2007 (John E. Savage)
Quantum Complexity Theory, MIT, Fall 2010 (Scott Aaronson)
Advanced Complexity Theory, MIT, Spring 2005 (Madhu Sudan)
Advanced Complexity Theory, MIT, Fall 2001 (Dan Spielman)
Theory of Computation, MIT, Fall 2006 (Michael Sipser)
Computational Complexity, TIFR, 2011-12 (Prahladh Harsha)
Computational Complexity, Stanford University, Spring 2010 (Luca Trevisan)
Computational Complexity, Tel Aviv University (Muli Safra)
Computational Complexity, University of Illinois, Spring 2009 (Manoj M. Prabhakaran)
Boolean Circuit Complexity, Tel Aviv University, Fall 1994-1995 (Uri Zwick)