Section outline

  • Collapse Expand

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

    Collapse all Expand all

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

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

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

    Διαλέξεις:

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

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

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

    • ΤΒΑ
  • Collapse Expand

    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.

  • Collapse Expand

    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]

  • Collapse Expand

    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]

  • Collapse Expand

    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]

  • Collapse Expand

    7 November - 13 November

    ΔΕΥΤΕΡΑ

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

    ΠΕΜΠΤΗ

    • Reductions & Completeness: completeness, closure under reductions.

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

  • Collapse Expand

    14 November - 20 November

    ΔΕΥΤΕΡΑ

    • Reductions & Completeness: NP-completeness.

    ΠΕΜΠΤΗ

    • Reductions & Completeness: Cook's Theorem.

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

  • Collapse Expand

    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 από εδώ.
  • Collapse Expand

    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]
  • Collapse Expand

    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]

     

  • Collapse Expand

    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 από εδώ.
  • Collapse Expand

    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].
  • Collapse Expand

    23 January - 29 January

    ΔΕΥΤΕΡΑ

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

     

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

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

     

  • Collapse Expand

    6 February - 12 February

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

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

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

    27 February - 5 March

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

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

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