Computer Science

This is last year syllabus. The syllabus may change, depending on the pace of the couse. _________________________________________________ SYLLABUS OF "COMPUTAIONAL COMPLEXITY 2022/2023" 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)

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]

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.

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