Computer Science

MASSIMO LAURIA

Educational goals

Introduction to the fundamental concepts of computational complexity
through rigorous mathematical tools. The main topics of the course:
the intractability of computational problems, models of computation
(Turing machines, Boolean circuits, decision trees, communication
complexity), the hierarchy of complexity classes (P, NP, coNP, BPP,
ZPP, the polynomial hierarchy), the P vs NP problem, NP-completeness,
interactive proof systems, and probabilistic methods.

Knowledge and understanding

Knowledge of the main models of computation and their associated
complexity measures. Understanding of techniques for proving lower
bounds and reducing problems. Ability to read and understand
mathematical proofs of a combinatorial and probabilistic nature,
typical of computational complexity theory.

Apply knowledge and understanding

Ability to apply reduction techniques to prove the NP-completeness or
NP-hardness of problems. Ability to use combinatorial and
probabilistic methods to derive complexity results in models such as
decision trees and communication complexity.

Making judgements

Ability to assess the inherent difficulty of a computational problem,
to identify the most appropriate model of computation for its
analysis, and to evaluate the correctness and effectiveness of
a complexity proof.

Communication skills

Oral presentation (in English, at the blackboard) of a proof of
NP-hardness or NP-completeness chosen from a list provided by the
instructor, approximately 20–25 minutes in length, delivered to fellow
course participants.

Learning skills

Ability to independently read advanced research articles and textbook
chapters in computational complexity theory, and to apply the
techniques learned to tackle new models and open problems in
the field.

The goal is to make the students understand the theoretical analysis of computation, in order to be able to adress and understand fundamental questions about computation and its efficiency. The students would improve the ability to prove mathematical theorems that answer or frame problems in computation.

Basic notions of discrete mathematics (counting, graphs, permutations, ) [important]
Notion of algorithm and data structure (Stack, queue, trees)[important]
Efficient algorithms exploiting data information (for instance, binary search)[important]
Basic notions of propositional logic [important]
Notion of Relation of generic arity[important]
Notion of universal and existential Quantification[important]
Concetto di Relazione di arità generica[important]
Basic notions of first order Logic[important]
Advanced Notions on Languages [important]
Computational models [important]
Basic Notions of Complexity Theory [importante]

This is the 2025/2026 syllabus. The syllabus may change, depending on the pace of the couse.

_________________________________________________

SYLLABUS OF "COMPUTAIONAL COMPLEXITY 2025/2026"

Massimo Lauria
_________________________________________________





1 Bibliography
==============

The main textbook of the course is

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

Additional material on communication complexity and proof complexity
are in

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

A proof from the last part of the course is only published, as far as
I know, in
- [K] Knuth, the Art of Computer Programming, Vol 4, fascicle 6, Page
55-56.

All reference to a textbook refer to book [AB] unless
specified otherwise.


2 Introduction
==============

- Introduction
- Chapter 0
- Parity on n variables requires CNF formulas of size Theta(n 2^n)
- Equality of two strings of n bits requires n bits of
communication


3 Turing machines, Universality, Uncomputability, the class P
=============================================================

- Sections 1.1, 1.2, 1.3, 1.4
- Sections 1.5, 1.6
- Exercises 1.2, 1.3, 1.5, 1.8, 1.14
- Read and ponder the statement of Exercise 1.6, 1.7 and 1.9


4 NP and NP-completeness
========================

- Karp reductions
- NP-completeness
- Non deterministic Turing Machines
- Cook-Levin theorem proved via Circuit-SAT (see Section 6.1)
- Decision vs Seach
- coNP, EXP, NEXP
- Implications of P vs NP
- Sections 2.1, 2.2, 2.3 (Section 2.3.4 is optional), 2.4, 2.5, 2.6,
2.7
- Section 6.1
- Exercises 2.1, 2.2, 2.4, 2.6, 2.7, 2.8, 2.9, 2.10, 2.11, 2.12, 2.14,
2.15, 2.16, 2.17, 2.18, 2.21, 2.23, 2.24, 2.25, 2.26, 2.27, 2.29,
2.30, 2.31, 2.34.


5 Time Hierarchy Theorems, Oracles
==================================

- Hierarchy theorem for deterministic time
- Hierarchy theorem for non-deterministic time (just the statement)
- Ladner theorem (just the statement)
- Turing Machines with oracles
- P vs NP does not relativize w.r.t. to Oracles
- Sections 3.1, 3.2, 3.3, 3.4


6 Space complexity, NL-completeness
===================================

- The Graph of configurations
- PSPACE, TQBF is PSPACE-complete
- Savitch's Theorem
- Lospace reductions and NL-completeness
- NL = coNL
- Sections 4.1, 4.2, 4.3
- Exercises 4.1, 4.2, 4.4, 4.5, 4.6, 4.7, 4.8, 4.9, 4.10, 4.11


7 Randomized computation, RP, coRP, BPP, ZPP
============================================

- Appendix A.2
- Sections 7.1, 7.2 (no 7.2.4), 7.3, 7.4, 7.5 (no 7.5.3)
- Exercises 7.1, 7.4, 7.5, 7.6


8 Interactive Proofs and PSPACE
===============================

- randomness in interaction is necessary
- public vs private randomness
- IP, AM, MA classes
- protocol for Graph Non Isomorphism
- coNP \(\in\) IP
- IP = PSPACE
- Sections 8.1, 8.2, 8.3
- Sections 8.2.2 and 8.2.3 are optional, but the statement of Theorems
8.12 and 8.13 are part of the program
- Exercises 8.1, 8.2, 8.6, 8.8


9 Circuits and Polynomial Hierarchy
===================================

- BPP vs P/poly
- BPP in the second level of the hierarchy
- Karp-Lipton theorem
- if GI is NP-complete, then PH collapses to second level
- Circuit size complexity
- Theorem 1.29 on Jukna's book [J]
- Sections 5.1, 5.2, 6.1, 6.2, 6.4, 6.5, 6.6, 7.5, 8.2.4
- Exercises 5.1, 6.3, 6.5, 6.6


10 Decision trees
=================

- decision trees
- worst case depth complexity
- certificate complexity
- just the statement that bs(f)

Main textbooks:

S. Arora B. Barak: Computational Complexity: A Modern Approach Cambridge University Press, 2007
S. Jukna. Boolean Function Complexity. Springer. 2012
A.Rao, A. Yehudayoff. Communication Complexity and Applications. Cambridge University Press, 2020

Other reference textbooks

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

Lecture will be live in class, with no recording whatsoever.
There will be student presentations, as part of the final evaluation.

Attending is not mandatory, but strongly suggested.
Nevertheless there will be a mandatory presentation in front of the class, which contributes to the final grade.

1. I quarter term blackboard presentations of a basic result.
2. Half-term homeworks
3. Final oral examinations.

Present the proof of Cook's Theorem

In the definition of BPP, what is the acceptable range for the probability of finding the right answer?