Weekly outline

  • Χειμερινό Εξάμηνο 2019-2020

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

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

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

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

  • 30 September - 6 October

    ΠΕΜΠΤΗ

    • Διοικητικά - Διαδικαστικά
    • Problems, Algorithms and Languages. Decision and optimization problems, Representation as strings.
    • Equivalence of Computational Models, Turing Machines.
    Reading:
    -Ch.1,2 from [1]

  • 7 October - 13 October

    ΔΕΥΤΕΡΑ

    • Time and Space bounds, multiple strings, linear speedup, nondeterminism.
    • The Universal Turing Machine, Simulation, Diagonalization The Halting Problem, Recursive and Recursive Enumerable Sets, Rice’s Theorem.



    ΠΕΜΠΤΗ

    • Complexity Classes: Complexity Measures, Time and Space Classes, Hierarchy Theorems, Gap Theorem, Succinct Certificates.
    • Space Computation: The classes L and NL, Savitch's Theorem, NL-completeness.


    Reading:
    -Ch.3, 7 from [1]

    • 14 October - 20 October

      ΔΕΥΤΕΡΑ

      • Space Computation: Immerman-Szelepscényi Theorem, Reingold’s Theorem: L = SL & Undirected REACHABILITY.



      ΠΕΜΠΤΗ

      • Different types of reductions (logspace, Karp, Cook), Circuits.


      Reading:
      -Ch.8 from [1]

      • 21 October - 27 October

        ΔΕΥΤΕΡΑ

        • P-completeness, NP-completeness, Cook’s Theorem, NP-complete problems, Logical Characterizations.



        ΠΕΜΠΤΗ

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


        Reading:
        -Section 14.3, Ch.17 from [1]

        • 28 October - 3 November

          ΔΕΥΤΕΡΑ

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



          ΠΕΜΠΤΗ

          • Randomized Computation: Randomized Algorithms,  BPP, RP, coRP, ZPP.


          Reading:
          -Sections 7.1, 7.2, 7.3 from [2]

          • 4 November - 10 November

            ΔΕΥΤΕΡΑ

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


            Reading:
            -Sections 7.4, 7.5 from [2]
            -Sections 6.1-6.6 from [2]

            • 11 November - 17 November

              ΔΕΥΤΕΡΑ

              • Non-Uniform Complexity: Parallel computation (classes NC, RNC, AC, TC).
              • Circuit Lower Bounds: Lower Bounds for AC0, Counting Circuits (ACC) and lower bounds, non-uniform lower bound for NEXP, Natural Proofs.



              ΠΕΜΠΤΗ


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


              Reading:
              -Section 6.7 from [2]
              - Sections 14.1 - 14.4 from [2]

            • 18 November - 24 November

              ΔΕΥΤΕΡΑ

              • 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)].
              Reading:
              -Ch.8 from [2]

              • 25 November - 1 December

                ΔΕΥΤΕΡΑ

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


                ΠΕΜΠΤΗ

                • The Structure of NP: density, sparse sets, Mahaney's Theorem

                Reading:
                -Sections 14.1, 14.2 from [1]

                • 2 December - 8 December

                  ΔΕΥΤΕΡΑ

                  • Circuit Lower Bounds: Håstad's Switching Lemma's proof, Natural arguments.


                  ΠΕΜΠΤΗ

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

                  • 9 December - 15 December

                    ΔΕΥΤΕΡΑ

                    • Circuit Lower Bounds: Lower bounds from algorithms (NEXP vs ACC0), Algorithms from lower bound techniques.


                    ΠΕΜΠΤΗ

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



                    • 16 December - 22 December

                      ΔΕΥΤΕΡΑ

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


                      ΠΕΜΠΤΗ

                      • Logic Paper Presentation.

                      • 23 December - 29 December

                        ΔΕΥΤΕΡΑ

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

                        • 6 January - 12 January

                          ΠΕΜΠΤΗ

                          • Counting Complexity: The class #P, parsimonious reductions, completeness results.

                          • 13 January - 19 January

                            ΔΕΥΤΕΡΑ


                            ΠΕΜΠΤΗ

                            • Counting Complexity: The class ⊕P,  Valiant-Vazirani Lemma.

                            • 20 January - 26 January

                              ΔΕΥΤΕΡΑ

                              • Derandomization of Complexity Classes: The Easy Witness Lemma proof.


                              ΠΕΜΠΤΗ

                              • Counting Complexity: Toda's Theorem, the class GapP and applications.

                              • 27 January - 2 February

                                ΔΕΥΤΕΡΑ

                                • Guest Lecture: 90 years of Computability and Complexity (Stathis Zachos)


                                ΠΕΜΠΤΗ

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

                                • 3 February - 9 February