Weekly outline

  • Χειμερινό Εξάμηνο 2024-2025

    Προσφέρεται ως "Υπολογιστική Πολυπλοκότητα" στην ΣΗΜΜΥ.

    Διδάσκοντες:

    Βοηθοί Διδασκαλίας:

    Διαλέξεις:
    • Δευτέρα 17:00-20:00 (Παλιά Κτίρια Ηλεκτρολόγων ΕΜΠ, Αίθουσα 1.1.31)
    • Πέμπτη 15:00-17:00 (Παλιά Κτίρια Ηλεκτρολόγων ΕΜΠ, Αίθουσα 1.1.31)

         Έναρξη μαθημάτων: 7/10/24


    Περιεχόμενο Μαθήματος:
    Basic notions and results in Complexity Theory. Oracles & The Polynomial Hierarchy. The structure of NP. Randomized Computation. Non-Uniform Complexity. Circuit Lower Bounds. Interactive Proofs. Probabilistically Checkable Proofs. Pseudorandomness and Derandomization of Complexity Classes. Circuit Lower Bounds for NEXP. Counting Complexity. A short introduction to Fine-Grained Complexity.


  • Εβδομάδα 1

    Δευτέρα 7 Οκτωβρίου

    • Basic notions and results of Complexity Theory: Problems, Turing Machines and their properties, Undecidability and Rice's Theorem.

    Πέμπτη 10 Οκτωβρίου

    • Basic notions and results of Complexity Theory: Complexity Measures, Complexity Classes, Hierarchy Theorems. 


    Μπορείτε να διαβάσετε:

    • Ch. 1,2,3 from [1]
    • Ch. 0,1 from [2]
    Δείτε επίσης:
    • Στην υποσελίδα "Βιβλιογραφία-Υλικό-Σύνδεσμοι" θα βρείτε τις αναφορές για την βιβλιογραφία ([1], [2]), άλλες πηγές και σημειώσεις διαλέξεων, online courses Πολυπλοκότητας και άλλο ενδιαφέρον υλικό.

    • Εβδομάδα 2

      Δευτέρα 14 Οκτωβρίου

      • Basic notions and results of Complexity Theory: Separating complexity classes via diagonalization, proving inclusion of complexity classes via simulation.  Overview of deterministic and nondeterministic time and space classes. Certificate characterizations.


      Πέμπτη 17 Οκτωβρίου

      • Basic notions and results of Complexity Theory: Reductions and completeness, space complexity basics, Savitch’s Theorem, Immerman-Szelepscényi Theorem.


      Μπορείτε να διαβάσετε:
      • Ch. 7 from [1]
      • Ch. 1,2,3 from [2]

      • Εβδομάδα 3

        Δευτέρα 21 Οκτωβρίου

        • Basic notions and results of Complexity Theory: NL-completeness, P-completeness, The Cook-Levin Theorem, NP-completeness, PSPACE-completeness, Logical Characterizations & Descriptive complexity.


        Πέμπτη 24 Οκτωβρίου

        • Oracles & The Polynomial Hierarchy: Oracles and oracle classes, Oracle worlds.

        Μπορείτε να διαβάσετε:
        • Section 14.3 from [1]
        • Ch. 17 from [1]


        Δείτε επίσης:

        • Εβδομάδα 4

          Δευτέρα 28 Οκτωβρίου

          Δεν έγινε μάθημα.


          Πέμπτη 31 Οκτωβρίου

          • Oracles & The Polynomial Hierarchy: The Polynomial Hierarchy, definition and properties.


          Μπορείτε να διαβάσετε:

          • Ch. 17 from [1]


          • Εβδομάδα 5

            Δευτέρα 4 Νοεμβρίου

            • Oracles & The Polynomial Hierarchy: The complexity of optimization problems, the class FPNP.


            Πέμπτη 7 Νοεμβρίου

            • The Structure of NP: Enumerations, Ladner’s Theorem.


            Μπορείτε να διαβάσετε:
            • Ch. 17 from [1]
            • Sections 14.1-14.2 from [1]

            • Εβδομάδα 6

              Δευτέρα 11 Νοεμβρίου

              • The Structure of NP: Enumerations, Applications of Ladner’s Theorem and effective presentability, Padding, NP-isomorphism, The “Berman-Hartmanis” conjecture.


              Πέμπτη 14 Νοεμβρίου

              Δεν έγινε μάθημα.


              Μπορείτε να διαβάσετε:

              • Sections 14.1-14.2 from [1]
              • Sections 2.6 from [2]



              • Εβδομάδα 7

                Δευτέρα 18 Νοεμβρίου

                • The Structure of NP: Proof of Ladner’s Theorem, Padding, Density, Sparse Sets, Mahaney's Theorem.


                Πέμπτη 21 Νοεμβρίου

                • Randomized Computation: Probabilistic Turing machines, the class BPP. The classes RP, coRP and ZPP. Quantifier notation and related results, the the class ZPP, semantic and syntactic classes, the “P vs BPP” question.


                Μπορείτε να διαβάσετε:
                • Sections 14.1-14.2 from [1]
                • Sections 7.1-7.5 from [2]

                • Εβδομάδα 8

                  Δευτέρα 25 Νοεμβρίου

                  • Non-Uniform Complexity: Boolean circuits, the class P/poly and related results, Turing Machines with advice


                  Πέμπτη 28 Νοεμβρίου

                  • Non-Uniform Complexity: Karp-Lipton Theorem, Algorithms for Circuit Analysis. 


                  Μπορείτε να διαβάσετε:
                  • Sections 6.1-6.7 from [2]



                  • Εβδομάδα 9

                    Δευτέρα 2 Δεκεμβρίου

                    • Non-Uniform Complexity: Boolean Functions, Circuit Lower Bounds, Kannan's Lower Bound.


                    Πέμπτη 5 Δεκεμβρίου

                    • Non-Uniform Complexity: Lower bounds for ACC0, lower bounds from algorithms (NEXP vs ACC0), Algorithms from lower bounds techniques. Monotone functions and circuit lower bounds. Natural proofs: the Circuit Complexity Barrier.

                    Μπορείτε να διαβάσετε:
                    • Sections 6.1-6.7 from [2]


                    Δείτε επίσης:

                    The Switching Lemma (Ryan O' Donnell)




                    • Εβδομάδα 10

                      Δευτέρα 9 Δεκεμβρίου

                      • Interactive Proofs: Deterministic verifiers, probabilistic verifiers and the class IP, public and private coins, Arthur-Merlin Games, the class AM and its properties


                      Πέμπτη 12 Δεκεμβρίου

                      • Interactive Proofs: Shamir's Theorem (IP=PSPACE), Probabilistically Checkable Proofs, The Class PCP[r(n),q(n)].


                      Μπορείτε να διαβάσετε:
                      • Sections 8.1-8.4 from [2]

                      • Εβδομάδα 11


                        Δευτέρα 16 Δεκεμβρίου

                        • Derandomization of Complexity Classes: The general derandomization paradigm, Pseudorandom Generators.


                        Πέμπτη 19 Δεκεμβρίου

                        • Derandomization of Complexity Classes: The Nisan-Wigderson Construction, Worst-case and average case hardness, Uniform Derandomization, consequences to Circuit Lower Bounds.

                        Μπορείτε να διαβάσετε:
                        • Section 20.1, 20.2 from [2]

                        • Εβδομάδα 13

                          Πέμπτη 9 Ιανουαρίου

                          • Derandomization of Complexity Classes: The Easy Witness Lemma Proof (1/2)

                          Μπορείτε να διαβάσετε:
                          • Section 20.3, 20.4 from [2]

                          • Εβδομάδα 14

                            Δευτέρα 13 Ιανουαρίου

                            • Derandomization of Complexity Classes: The Easy Witness Lemma Proof (2/2)

                            Πέμπτη 16 Ιανουαρίου

                            • An Introduction to Fine-Grained Complexity