Computer Science - Informatica

Questo è il programma dell'anno precedente. Il programma potrà subire variazioni. _________________________________________________ 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)

PREREQUISTI ITA Concetti di base di Matematica Discreta (conteggi, grafi, permutazioni, ) [importante] Concetti di algoritmo e di strutture dati (pile, code, alberi)[importante] Algoritmi efficienti in presenza di informazioni aggiuntive (esempio ricerca binaria) [importante] Nozioni di base di Logica proposizionale[importante] Concetto di Relazione di arità generica[importante] Concetti di Quantificatore esistenziale ed universale[importante] Nozioni di base di Logica del primo ordine [importante] Nozioni di Linguaggi[importante] Modelli di computazione [importante] Nozioni di Base di Complessità [importante]

Testi principali: 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 Altri testi complementari 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.

Le lezioni saranno in presenza, frontali e in aula. Non ci saranno registrazioni. Ci saranno (come parte della valutazione finale) delle presentazioni di studenti

La frequenza è consigliata fortemente ma non è obbligatoria. Comunque ci saranno delle presentazioni da fare in aula per la valutazione finale.

1.Presentazione alla lavagna di risultati semplici (durante il corso) 2. Compito per casa di metà corso 3. Prova orale finale

Le lezioni saranno in presenza, frontali e in aula. Non ci saranno registrazioni. Ci saranno (come parte della valutazione finale) delle presentazioni di studenti

Questo è il programma dell'anno precedente. Il programma potrà subire variazioni. _________________________________________________ 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)

PREREQUISTI ITA Concetti di base di Matematica Discreta (conteggi, grafi, permutazioni, ) [importante] Concetti di algoritmo e di strutture dati (pile, code, alberi)[importante] Algoritmi efficienti in presenza di informazioni aggiuntive (esempio ricerca binaria) [importante] Nozioni di base di Logica proposizionale[importante] Concetto di Relazione di arità generica[importante] Concetti di Quantificatore esistenziale ed universale[importante] Nozioni di base di Logica del primo ordine [importante] Nozioni di Linguaggi[importante] Modelli di computazione [importante] Nozioni di Base di Complessità [importante]

Testi principali: 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 Altri testi complementari 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.

Le lezioni saranno in presenza, frontali e in aula. Non ci saranno registrazioni. Ci saranno (come parte della valutazione finale) delle presentazioni di studenti

La frequenza è consigliata fortemente ma non è obbligatoria. Comunque ci saranno delle presentazioni da fare in aula per la valutazione finale.

1.Presentazione alla lavagna di risultati semplici (durante il corso) 2. Compito per casa di metà corso 3. Prova orale finale

Le lezioni saranno in presenza, frontali e in aula. Non ci saranno registrazioni. Ci saranno (come parte della valutazione finale) delle presentazioni di studenti