Weekly outline

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

  • 13 October - 19 October

    ΔΕΥΤΕΡΑ

    • Ιστορική Εισαγωγή: Hierarchies of Complexity Classes
    • Διοικητικά - Διαδικαστικά

    ΠΕΜΠΤΗ

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

    Προτεινόμενο Διάβασμα:

    • p. 3-26 από το [1]

    Μπορείτε να δείτε επίσης:

    • Invitation to complexity theory, Oded Goldreich (link)
    • Mute
      Current Time 0:00
      /
      Duration Time 0:00
      Loaded: 0%
      Progress: 0%
      Stream TypeLIVE
      Remaining Time -0:00
       

    • 20 October - 26 October

      ΔΕΥΤΕΡΑ

      • Computability & Undecidability: The Universal Turing Machine, Simulation, Diagonalization
        The Halting Problem, Recursive and Rec. Enumerable sets, Rice's Theorem

      Προτεινόμενο Διάβασμα:

      • p. 57-63 από το [1].

      ΠΕΜΠΤΗ

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

      Προτεινόμενο Διάβασμα:

      • p. 139-151 από το [1]

      • 27 October - 2 November

        ΔΕΥΤΕΡΑ

        • Space Computation: Immerman-Szelepscényi Theorem, NL-completeness

        Προτεινόμενο Διάβασμα:

        • p. 151-153 από το [1]
        • Chapter 3 aπό το [2]

        ΠΕΜΠΤΗ

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

        Προτεινόμενο Διάβασμα:

        • p. 159-172 από το [1]

      • 3 November - 9 November

        ΔΕΥΤΕΡΑ

        • Θ. Λιανέας (NTUA): Reingold's Theorem: Undirected Reachability in Logspace
        • Ομιλίες φοιτητών:
          - Θ. Παπαμακάριος: NP-complete Problems: Cook's Theorem, SAT and Satisfiability variants.

        ΠΕΜΠΤΗ

        • Ομιλίες φοιτητών:
          - M. Πετροπαναγιωτάκη: NP-complete Problems: IS, CLIQUE, MAX-CUT
          - Δ. Διαμαντής: NP-complete Problems: IS, CLIQUE, MAX-CUT

      • 10 November - 16 November

        ΔΕΥΤΕΡΑ

        • Ομιλίες φοιτητών:
          - Ι. Λιβιεράτος: NP-complete Problems: 3DM, Knapsack, Pseudopolynomial Algorithms and Strong NP-completeness
          - Β. Βελώνα: Ladner's Theorem, Density, Sparse Sets

        Προτεινόμενο Διάβασμα:

        • Chapter 9 από το [1]
        • Sections 14.1, 14.2 (p. 329-339) από το [1]

         

        ΠΕΜΠΤΗ

        • Ομιλίες φοιτητών:
          - Κ. Ζαμπετάκης: The "Berman-Hartmanis" Conjecture, NP-isomorphism, padding
          - Ν. Κωτσάνη: Second-Order Logic, Undecidability-Incompleteness, Fagin’s Theorem

          Προτεινόμενο Διάβασμα:

          • p. 173-176 από το [1]

      • 17 November - 23 November

        ΔΕΥΤΕΡΑ

        Αργία

        ΠΕΜΠΤΗ

        1ο Quiz

        Ύλη:
        - Το 1ο set διαφανειών του μαθήματος
        - Από το βιβλίο του Παπαδημητρίου [1]:
        -- Sections 2.1-2.5, 2.7
        -- Chapter 3 (όχι σελ. 64,65)
        -- Chapter 7
        -- Section 8.1-8.2
        • Ομιλίες φοιτητών:
          - Κ. Ζαμπετάκης (συν.): Mahaney's Theorem

      • 24 November - 30 November

        ΔΕΥΤΕΡΑ

        • Ομιλίες φοιτητών:
          - Κ. Ζαμπετάκης (συν.): Mahaney's Theorem
          - Ν. Κωτσάνη (συν.): Fagin’s Theorem

        ΠΕΜΠΤΗ

        Δεν θα γίνει μάθημα λόγω απεργίας!

        • 1 December - 7 December

          ΔΕΥΤΕΡΑ

          • Ομιλίες Φοιτητών:
            - Σ. Σκουλάκης: Function Problems: The classes coNP and ΔNP, Function classes and reductions, the classes PLS and PPAD.

          ΠΕΜΠΤΗ

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

          Προτεινόμενο Διάβασμα:

          • Sections 7.1-7.3 (p. 123-132) από το [2]
          • Section 1 από εδώ.

        • 8 December - 14 December

          ΔΕΥΤΕΡΑ

          • Randomized Computation: Error Reduction, The Class PP, Relativized Results
          • Oracles and Oracle Classes. Relativizations.

          Προτεινόμενο Διάβασμα:

          • Sections 7.4, 7.5 (p. 132-138) από το [2]
          • p. 256-257 (class PP) από το [1]
          • Section 14.3 (p. 339-343) από το [1]

          ΠΕΜΠΤΗ

          • Interactive Proofs: Interactive Proof Systems, the class IP[k]

          Προτεινόμενο Διάβασμα:

          Section 8.1 από το [2]

          • 15 December - 21 December

            ΔΕΥΤΕΡΑ

            • Interactive Proofs: IPs, Arthur-Merlin Games, Quantifier Notation and related results

            Προτεινόμενο Διάβασμα:

            Section 8.2 από το [2]
            Section 2 από εδώ.

            ΠΕΜΠΤΗ

            • Shamir's Theorem

              Προτεινόμενο Διάβασμα:

              Section 8.3 από το [2]

            • Probabilistically Checkable Proofs

            Προτεινόμενο Διάβασμα:

            Section 11.1, 11.2 από το [2]

            • 22 December - 28 December

              ΔΕΥΤΕΡΑ

              • Μανώλης Ζαμπετάκης (ΜΙΤ): Dinur's Proof of the PCP Theorem

            • 5 January - 11 January

              ΠΕΜΠΤΗ

              • Oracles & Optimization Problems
              • The Polynomial Hierarchy

              • 12 January - 18 January

                ΔΕΥΤΕΡΑ

                • Non-Uniform Complexity: Boolean Circuits, the class P/poly, Advice Turing Machines, Circuit Lower Bounds, Natural Proofs

                ΠΕΜΠΤΗ

                • Counting Complexity: The Class #P, #P-completeness & The Permanent, Other Counting Classes, Gaps

                • 19 January - 25 January

                  ΔΕΥΤΕΡΑ

                  • Counting Complexity: Counting problems with easy decision, the class #PE, the class TotP

                  ΠΕΜΠΤΗ

                  • Counting Complexity: Operators on Complexity Classes, Valiant-Vazirani Theorem, Toda's Theorem
                  • Ομιλίες φοιτητών:
                    Ι. Παπαϊωάννου: Zero-Knowledge Proofs

                  • 26 January - 1 February

                    ΔΕΥΤΕΡΑ

                    • Ομιλίες φοιτητών:
                      Χ. Τζόβας: Algebraic Computation
                      Λ. Ζακυνθινού                      : PCPs & Inapproximability


                    ΠΕΜΠΤΗ

                    • 2o Quiz
                    • Toda's Theorem

                  • 2 February - 8 February

                    ΔΕΥΤΕΡΑ

                    • Ομιλίες φοιτητών:
                      Μ. Σάμαρης: Average-Case Complexity
                      Δ. Τσίπρας: Fourier Analysis & Inapproximability

                    ΠΕΜΠΤΗ

                    • Ομιλίες φοιτητών:
                      Ο. Κωνσταντινίδης & Μ. Κουβαράς: Quantum Computation