Weekly outline

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

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

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

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

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


    Περιεχόμενο Μαθήματος:
    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

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

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

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

    • 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

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

      • Basic notions and results of Complexity Theory: Complexity Measures, Complexity Classes, Hierarchy Theorems. Separating complexity classes via diagonalization, proving inclusion of complexity classes via simulation.


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

      • Basic notions and results of Complexity Theory: Reductions and completeness, space complexity basics. Overview of deterministic and nondeterministic time and space classes.


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




      • Εβδομάδα 3

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

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


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

        • Oracles & The Polynomial Hierarchy: The polynomial-time hierarchy and related theorems.

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


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

        • Εβδομάδα 4

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

          • Oracles & The Polynomial Hierarchy: The complexity of optimization problems, the class FPNP.
          • The Structure of NP: Enumerations, Ladner’s Theorem, Padding, NP-isomorphism, The “Berman-Hartmanis” conjecture.


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

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

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

          • Εβδομάδα 5

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

            • The Structure of NP: Mahaney's Theorem.

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


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

            • Randomized Computation: 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]

            • Εβδομάδα 6

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

              • Randomized Computation: Semantic and syntactic classes, the “P vs BPP” question, Relativized Results.


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

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


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

              • Sections 7.1-7.5 from [2]
              • Sections 6.1-6.7 from [2]



              • Εβδομάδα 7

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

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


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

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


                • Εβδομάδα 8

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

                  • Non-Uniform Complexity: Circuit Classes, Uniform circuit families and parallel computations. 


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

                  • Non-Uniform Complexity: Håstad’s Switching Lemma and applications to lower bounds for parity, oracle worlds, computational learning and decision tree complexity. The polynomial approximation method.


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

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

                  The Switching Lemma (Ryan O' Donnell)




                  • Εβδομάδα 9

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

                    • 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.


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

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

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