Weekly outline

  • Χειμερινό Εξάμηνο 2016-2017

    Προσφέρεται ως "Θεωρητική Πληροφορική Ι: Αλγόριθμοι και Πολυπλοκότητα" στην ΣΗΜΜΥ, και ως "Αλγόριθμοι και Πολυπλοκότητα ΙΙ" στο ΜΠΛΑ.

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

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

    Διαλέξεις:

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

    Έναρξη: Δευτέρα, 10 Οκτωβρίου 2016

    Ώρες Γραφείου:

    • ΤΒΑ

  • 10 October - 16 October

    ΔΕΥΤΕΡΑ

    • Διοικητικά - Διαδικαστικά
    • Hierarchies of Complexity Classes (Course overview)
    • Introduction to Complexity Theory.
    • Problems, Algorithms and Languages. Decision and optimization problems.
    • Turing machines with multiple strings, linear speedup, nondeterminism.
    • Equivalence of Computational Models, Turing Machines, Representation as strings.
    • Computability & Undecidability: The Universal Turing Machine, Simulation, Diagonalization

    ΠΕΜΠΤΗ

    • Introduction to Complexity Theory.
    • Problems, Algorithms and Languages. Decision and optimization problems.

    • 17 October - 23 October

      ΔΕΥΤΕΡΑ

      • Turing machines with multiple strings, linear speedup, nondeterminism.
      • Equivalence of Computational Models, Turing Machines, Representation as strings.
      • Computability & Undecidability: The Universal Turing Machine, Simulation, Diagonalization

      ΠΕΜΠΤΗ

      • Complexity Classes: Complexity Measures, Time and Space Classes, Hierarchy Theorems, Gap Theorem.

      Προτεινόμενη Μελέτη:
      -Ch.1,2 από το [1]
      -Ch.3: p. 57-63 από τo [1]
      -Ch. 7: p.139-146 από το [1]
      - Ch.1 από το [2]

      • 24 October - 30 October

        ΔΕΥΤΕΡΑ

        • Space Computation: The classes L and NL, Savitch's Theorem, NL-completeness

        ΠΕΜΠΤΗ

        • Space Computation: Immerman-Szelepscényi Theorem

        Προτεινόμενη Μελέτη:
        - Ch.7:  p. 146-153 από το [1]
        -Ch.4 από το [2]

        • 31 October - 6 November

          ΔΕΥΤΕΡΑ

          • Oracles, Oracle Turing Machines and Oracle Classes, Relativizations, The Limits of Diagonalization.

          ΠΕΜΠΤΗ

          • The Polynomial Hierarchy: Definition, Main Properties, Collapsion and consequences.

          Προτεινόμενη Μελέτη:
          -Ch. 14: Section 14.3 από το [1]
          - Ch. 17: Section 17.2 από το [1]
          - Ch.3: Section 3.4 από το [2]

          • 7 November - 13 November

            ΔΕΥΤΕΡΑ

            • Reductions & Completeness: Different types of reductions and relations among them.

            ΠΕΜΠΤΗ

            • Reductions & Completeness: completeness, closure under reductions.

            Προτεινόμενη Μελέτη:
            -Ch.8,9 από το [1]

            • 14 November - 20 November

              ΔΕΥΤΕΡΑ

              • Reductions & Completeness: NP-completeness.

              ΠΕΜΠΤΗ

              • Reductions & Completeness: Cook's Theorem.

              Προτεινόμενη Μελέτη:
              -Ch.8,9 από το [1]

              • 21 November - 27 November

                ΔΕΥΤΕΡΑ

                • Randomized Computation: The classes BPP, RP, coRP

                 

                ΠΕΜΠΤΗ

                • Randomized Computation: The classes ZPP, RP, coRP, and relations among them, Quantifier Notation ane related results, The BPP-Theorem, the "P vs BPP Question".

                Προτεινόμενη Μελέτη:

                • Ch 7: Sections 7.1,7.2 από το [2]
                • Section 1 από εδώ.

                • 28 November - 4 December

                  ΔΕΥΤΕΡΑ
                  • Randomized Computation: Syntactic and semantic classes, Error Reduction, The Class PP, Relativized Results.

                   

                  ΠΕΜΠΤΗ

                  • Non-Uniform Complexity: Boolean Circuits, the class P/poly, Advice Turing Machines

                  Προτεινόμενη Μελέτη:

                  • Ch 7: Sections 7.1,7.2 από το [2]
                  • Section 1 από εδώ.
                  • Ch 6: Sections 6.1-6.5 από το [2]

                  • 5 December - 11 December

                    ΔΕΥΤΕΡΑ

                    • Non-Uniform Complexity: Circuit Lower Bounds, Natural Proofs

                     

                    ΠΕΜΠΤΗ

                    • Interactive Proofs: Deterministic verifiers, probabilistic verifiers and the class IP, Public and private coins, Arthur-Merlin Games

                     

                    Προτεινόμενη Μελέτη:

                    • Ch 6: Sections 6.1-6.5 από το [2]
                    • Ch 8: Section 8.1, 8.2 από το [2]

                     

                    • 9 January - 15 January

                      ΔΕΥΤΕΡΑ

                      • Interactive Proofs: The Class AM, Quantifier Notation, Perfect Completeness for AM

                       

                      ΠΕΜΠΤΗ

                      • Interactive Proofs: Collapsion of AM[k] hierarchy to AM=AM[2], Relativized results

                      Προτεινόμενη Μελέτη:

                      • Ch 8: Sections 8.1-8.2 από το [2]
                      • Section 2 από εδώ.

                      • 16 January - 22 January

                        ΔΕΥΤΕΡΑ

                        • Interactive Proofs: Shamir's Theorem (IP=PSPACE)

                         

                        ΠΕΜΠΤΗ

                        • Counting Complexity: Counting vs Decision Problems, the class #P, #SAT, PERMANENT, Parsimonious, Cook and Cook[1] (metric) reductions for Counting Problems, Valiant-Vazirani Theorem

                        Προτεινόμενη Μελέτη:

                        • Ch 8: Section 8.3 από το [2]
                        • Chapter 18 από το [1].

                        • 23 January - 29 January

                          ΔΕΥΤΕΡΑ

                          • Interactive Proofs: Quantifiers vs Counting: Toda's Theorem.

                           

                          Προτεινόμενη Μελέτη:

                          • Chapter 18 από το [1].

                           

                          • 6 February - 12 February

                            ΔΕΥΤΕΡΑ 6 ΦΕΒΡΟΥΑΡΙΟΥ

                            Ομιλίες Φοιτητών (1/2):

                            • Average-Case Complexity (Αλέξανδρος Ζαχαράκης)
                            • Pseudorandomness (Πλάτων Παπαδόπουλος)
                            • Communication Complexity (Ιωσήφ Μουλίνος)

                            • 27 February - 5 March

                              ΤΕΤΑΡΤΗ 1 ΜΑΡΤΙΟΥ

                              Ομιλίες Φοιτητών (2/2):

                              • Quantum Computation (Γιώργος Πιτσιλαδής)
                              • Function Problems (Ανθή Κορρέ)
                              • Zero-Knowledge Proofs (Κατερίνα Νικλάνοβιτς)
                              • Proof Complexity (Αριστοτέλης Χανιώτης)
                              • PCPs and Inapproximability (Παναγιώτης Πατσιλινάκος)
                              • Alternation (Νίκος Καραγιάννης-Αξυπολιτίδης)