Weekly outline

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

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

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

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

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


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

  • 2 October - 8 October

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

    • Συνάντηση γνωριμίας
    • Περιεχόμενο Μαθήματος
    • 9 October - 15 October

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

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

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


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

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

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

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


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

        • Basic notions and results of Complexity Theory: Certificate Characterization of NP, Efficient verification. Space Complexity (main results). Reductions.

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

        • 23 October - 29 October

          Δευτέρα

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

          Πέμπτη

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


          • 30 October - 5 November

            Δευτέρα

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

            Πέμπτη

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


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

            • 6 November - 12 November

              Δευτέρα

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

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

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

              Πέμπτη

              • Oracles & The Polynomial Hierarchy: The complexity of optimization problems, the class FPNP.
              • The Structure of NP: Enumerations, Ladner’s Theorem.

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


              • 13 November - 19 November

                Δευτέρα

                • The Structure of NP: Padding, NP-isomorphism, The “Berman-Hartmanis” conjecture, density, sparse sets.

                Πέμπτη

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


                • 20 November - 26 November

                  Δευτέρα

                  • The Structure of NP: Mahaney's Theorem.


                  Πέμπτη

                  • Randomized Computation: Probabilistic Turing machines, the classes BPP, RP, coRP and ZPP.
                  • 27 November - 3 December

                    Δευτέρα

                      • Randomized Computation: Quantifier notation and related results, semantic and syntactic classes, the “P vs BPP” question.
                      • Non-Uniform Complexity: Boolean circuits, the class P/poly and related results, Turing Machines with advice, Karp-Lipton Theorem


                      Πέμπτη

                      • Non-Uniform Complexity: Uniform circuit families and parallel computations (S. Zachos)


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

                      • 4 December - 10 December

                        Δευτέρα

                        • Non-Uniform Complexity: Circuit Complexity review, Algorithms for Circuit Analysis.

                        Πέμπτη

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

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


                          Δευτέρα

                          • Circuit Lower Bounds: Håstad’s Switching Lemma and applications to lower bounds for parity, oracle worlds, computational learning and decision tree complexity.

                          Πέμπτη

                          • Circuit Lower Bounds: The polynomial approximation method, lower bounds for ACC0, lower bounds from algorithms (NEXP vs ACC0), Algorithms from lower bounds techniques.


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

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

                          The Switching Lemma (Ryan O' Donnell)



                          • 18 December - 24 December

                            Δευτέρα

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

                            Πέμπτη

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


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

                            • 8 January - 14 January

                              Δευτέρα


                              Πέμπτη

                              • Derandomization of Complexity Classes: The Nisan-Wigderson Construction, Worst-case and average case hardness.
                              • Παρουσιάσεις φοιτητών.
                              • 15 January - 21 January

                                Δευτέρα

                                • Derandomization of Complexity Classes: Uniform Derandomization, consequences to Circuit Lower Bounds.
                                • Παρουσιάσεις φοιτητών.


                                Πέμπτη

                                • Derandomization of Complexity Classes: The Easy Witness Lemma
                                • Παρουσιάσεις φοιτητών.

                                • 22 January - 28 January

                                  Δευτέρα

                                  • Παρουσιάσεις φοιτητών.


                                  Πέμπτη (αναβλήθηκε για 2/2/23, λόγω καιρικών συνθηκών)

                                  • Παρουσιάσεις φοιτητών.