Massimo Lauria

  • massimo.lauria@uniroma1.it
  • +39-06-49910496
  • Room 9 - 4th floor - Dip.Science Statistiche
  • Office hours: Thu 11.00-13.00 (write email first)

Calendar and lecture room

  • Monday, 14.00-17.00 (room T1, RM113)
  • Wednesday, 14.00-16.00 (room T1, RM113)

In building E, in Viale Regina Elena, 295.

The course starts on September 19th, and goes on for 24 lectures up until, roughly, December 22nd. There is a Google Calendar of the lectures.

Course description

Computational complexity studies the intractability and the inherent complexity of computational problems. Some problems have efficient algorithms and solutions, while some others seem not to have any. While this could just be due to the lack of creativity, there are problems for which it is conjectured that such efficient algorithms do not exists at all.

In this course we study several computational model in which we can say interesting things about problems, in order to characterize their hardness. We discuss the famouse P vs NP problem.

The course has a strong mathematical flavor and requires mathematical maturity and some confidence with combinatorial and probabilistic methods. It is also useful to have had some preliminary exposure to algorithm courses.

Bibliography

The main textbook of the course is

  • [AB] Arora, Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2007.

Additional material may be drawn from

  • [J] Jukna. Boolean Function Complexity. Springer, 2012.
  • [RY] Rao, Yehudayoff. Communication Complexity and Applications. Cambridge University Press, 2020.

Not required but useful references

  • Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press, 2008.
  • Goldreich. P, NP, and NP-Completeness: The Basics of Computational Complexity. Cambridge University Press, 2010.
  • Krajicek. Proof Complexity. Cambridge, 2019.
  • Kushilevitz, Nisan. Communication Complexity. Cambridge University Press, 2006.
  • Papadimitriou. Computational Complexity. Pearsons, 1994.
  • Vollmer. Introduction to Circuit Complexity: an uniform approach/. Springer, 2013
  • Wigderson. Mathematics and Computation. Princeton University Press, 2019

Course program

The actual program of the course will develop during the semester.