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

  • Tuesday, 11.00-13.00 (room G50 RM115-E01P03L001)
  • Thursday, 16.00-19.00 (room T1 RM113-E01PTEL001)

Respectively at the 3rd floor of buildings G and at the ground floor of building E, in Viale Regina Elena, 295.

The course should start on September 24rd, and go on until December 19th. There is a Google Calendar of the lectures.

Updates: there will be no Computational Complexity class on October 15th and 17th, 2024, due to the teacher being away.

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

Program of the course

The full content of the course is described in the course journal.