Weekly outline

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

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

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

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

    Διαλέξεις:

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

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

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

    • ΤΒΑ

  • 12 October - 18 October

    ΔΕΥΤΕΡΑ

    • Διοικητικά - Διαδικαστικά
    • 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

    ΠΕΜΠΤΗ

    • The Halting Problem, Recursive and Rec. Enumerable sets, Rice's Theorem
    • 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]

    • 19 October - 25 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]

      • 26 October - 1 November

        ΔΕΥΤΕΡΑ

        • Reductions & NP-Completeness: Different types of reductions and relations among them, NP-completeness

        ΠΕΜΠΤΗ

        • Oracles & Optimization Problems (1/2), Relativizations.

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

        • 2 November - 8 November

          ΔΕΥΤΕΡΑ

          • Oracles & Optimization Problems (2/2), The Limits of Diagonalization

          ΠΕΜΠΤΗ

          • The Polynomial Hierarchy (1/2)

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

          • 9 November - 15 November

            ΔΕΥΤΕΡΑ

            • The Polynomial Hierarchy (2/2)

            ΠΕΜΠΤΗ

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

            • 16 November - 22 November

              ΔΕΥΤΕΡΑ

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

              ΠΕΜΠΤΗ

              • Randomized Computation: The classes BPP, RP, coRP

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

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

              • 23 November - 29 November

                ΔΕΥΤΕΡΑ

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

                 

                ΠΕΜΠΤΗ

                • Randomized Computation: Syntactic and semantic classes, Error Reduction, The Class PP, Relativized Results.

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

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

                • 30 November - 6 December

                  ΔΕΥΤΕΡΑ

                  • Non-Uniform Complexity: Boolean Circuits, the class P/poly, Advice Turing Machines, Circuit Lower Bounds, Natural Proofs, Advice Turing Machines, 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]

                  • 7 December - 13 December

                    ΔΕΥΤΕΡΑ

                    • Interactive Proofs: The Class AM, Quantifier Notation, Perfect Completeness for AM, Collapsion of AM[k] hierarchy to AM=AM[2], Relativized results

                     

                    ΠΕΜΠΤΗ

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

                     

                    • 14 December - 20 December

                      ΔΕΥΤΕΡΑ

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

                       

                      ΠΕΜΠΤΗ

                      • Interactive Proofs: The PCP Theorem ( NP=PCP[logn,1] ), Dinur's Proof (guest lecture by M. Zampetakis)

                       

                    • 21 December - 27 December

                      ΔΕΥΤΕΡΑ

                      • 1o Quiz

                      • 4 January - 10 January

                        ΠΕΜΠΤΗ

                        • Counting Complexity: Counting vs Decision Problems, the class #P

                        • 11 January - 17 January

                          ΔΕΥΤΕΡΑ

                          Δεν έγινε μάθημα, οι φοιτητές προσκλήθηκαν στην ημερίδα AtheCrypt 2016

                          ΠΕΜΠΤΗ

                          • Counting Complexity: Counting Problems, #SAT, PERMANENT, Parsimonious, Cook and Cook[1] (metric) reductions for Counting Problems, Valiant-Vazirani Theorem, Quantifiers vs Counting: Toda's Theorem.

                          • 18 January - 24 January

                            ΔΕΥΤΕΡΑ

                            • Uniform and Non-Uniform Derandomization of Complexity Classes (guest lecture by A. Antonopoulos)

                            ΠΕΜΠΤΗ (21/1)

                            Δεν θα γίνει μάθημα

                            • 25 January - 31 January

                              ΔΕΥΤΕΡΑ (25/1)

                              • Ομιλίες Φοιτητών: 
                                -- Ορέστης Παπαδιγενόπουλος
                                -- Δημήτρης Καλημέρης

                              ΠΕΜΠΤΗ (28/1)

                              • Ομιλίες Φοιτητών: 
                                -- Σταύρος Πετσαλάκης
                                -- Κυριάκος Αξιώτης

                              • 1 February - 7 February

                                ΔΕΥΤΕΡΑ (1/2)

                                • Ομιλίες Φοιτητών: 
                                  -- Βασίλης Παπαϊωάννου
                                  -- Μάκης Αρσένης