Section outline

  • Collapse Expand

    Χειμερινό Εξάμηνο 2022-2023

    Collapse all Expand all

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

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

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

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


    Περιεχόμενο Μαθήματος:
    Basic notions and results in Complexity Theory. Oracles & The Polynomial Hierarchy. The structure of NP. Randomized Computation. Non-Uniform Complexity. Circuit Lower Bounds. Interactive Proofs. Probabilistically Checkable Proofs. Pseudorandomness and Derandomization of Complexity Classes. Circuit Lower Bounds for NEXP. Counting Complexity. A short introduction to Fine-Grained Complexity.

  • Collapse Expand

    2 October - 8 October

    Πέμπτη 6 Οκτωβρίου

    • Συνάντηση γνωριμίας
    • Περιεχόμενο Μαθήματος
  • Collapse Expand

    9 October - 15 October

    Δευτέρα 10 Οκτωβρίου

    • Basic notions and results of Complexity Theory: Problems, Turing Machines and their properties, Undecidability and Rice's Theorem

    Μπορείτε να διαβάσετε:
    • Ch. 1,2,3 from [1]
    • Ch. 0,1 from [2]
    Δείτε επίσης:
    • Στην υποσελίδα "Βιβλιογραφία-Υλικό-Σύνδεσμοι" θα βρείτε τις αναφορές για την βιβλιογραφία ([1], [2]), άλλες πηγές και σημειώσεις διαλέξεων, online courses Πολυπλοκότητας και άλλο ενδιαφέρον υλικό.


    Πέμπτη 13 Οκτωβρίου

    • Basic notions and results of Complexity Theory: Complexity Measures, Complexity Classes, Hierarchy Theorems. Separating complexity classes via diagonalization, proving inclusion of complexity classes via simulation.

    Μπορείτε να διαβάσετε:
    • Ch. 7 from [1]
    • Ch. 1,2,3 from [2]
  • Collapse Expand

    16 October - 22 October

    Δευτέρα 17 Οκτωβρίου


    Πέμπτη 20 Οκτωβρίου

    • Basic notions and results of Complexity Theory: Certificate Characterization of NP, Efficient verification. Space Complexity (main results). Reductions.

    Μπορείτε να διαβάσετε:
    • Ch. 7 from [1]
    • Ch. 1,2,3 from [2]
    Δείτε επίσης:

  • Collapse Expand

    23 October - 29 October

    Δευτέρα

    • Basic notions and results of Complexity Theory: Reductions and completeness, space complexity basics. Overview of deterministic and nondeterministic time and space classes.

    Πέμπτη

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


  • Collapse Expand

    30 October - 5 November

    Δευτέρα

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

    Πέμπτη

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


    Μπορείτε να διαβάσετε:
    • Section 14.3 from [1]
    • Ch. 17 from [1]

  • Collapse Expand

    6 November - 12 November

    Δευτέρα

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

    Μπορείτε να διαβάσετε:
    • Section 14.3 from [1]
    • Ch. 17 from [1]

    Δείτε επίσης:

    Πέμπτη

    • Oracles & The Polynomial Hierarchy: The complexity of optimization problems, the class FPNP.
    • The Structure of NP: Enumerations, Ladner’s Theorem.

    Μπορείτε να διαβάσετε:
    • Sections 14.1-14.2 from [1]


  • Collapse Expand

    13 November - 19 November

    Δευτέρα

    • The Structure of NP: Padding, NP-isomorphism, The “Berman-Hartmanis” conjecture, density, sparse sets.

    Πέμπτη

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


  • Collapse Expand

    20 November - 26 November

    Δευτέρα

    • The Structure of NP: Mahaney's Theorem.


    Πέμπτη

    • Randomized Computation: Probabilistic Turing machines, the classes BPP, RP, coRP and ZPP.
  • Collapse Expand

    27 November - 3 December

    Δευτέρα

      • 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, Karp-Lipton Theorem


      Πέμπτη

      • Non-Uniform Complexity: Uniform circuit families and parallel computations (S. Zachos)


      Μπορείτε να διαβάσετε:
      • Sections 7.1-7.5 from [2]

    • Collapse Expand

      4 December - 10 December

      Δευτέρα

      • Non-Uniform Complexity: Circuit Complexity review, Algorithms for Circuit Analysis.

      Πέμπτη

      • Non-Uniform Complexity: Boolean Functions, Circuit Lower Bounds, Kannan's Lower Bound

      Μπορείτε να διαβάσετε:
      • Sections 6.1-6.7 from [2]
    • Collapse Expand

      11 December - 17 December


      Δευτέρα

      • Circuit Lower Bounds: Håstad’s Switching Lemma and applications to lower bounds for parity, oracle worlds, computational learning and decision tree complexity.

      Πέμπτη

      • Circuit Lower Bounds: The polynomial approximation method, lower bounds for ACC0, lower bounds from algorithms (NEXP vs ACC0), Algorithms from lower bounds techniques.


      Μπορείτε να διαβάσετε:
      • Sections 14.1-14.4 from [2]

      Δείτε επίσης:

      The Switching Lemma (Ryan O' Donnell)



    • Collapse Expand

      18 December - 24 December

      Δευτέρα

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


      Μπορείτε να διαβάσετε:
      • Sections 8.1-8.4 from [2]

    • Collapse Expand

      8 January - 14 January

      Δευτέρα


      Πέμπτη

      • Derandomization of Complexity Classes: The Nisan-Wigderson Construction, Worst-case and average case hardness.
      • Παρουσιάσεις φοιτητών.
    • Collapse Expand

      15 January - 21 January

      Δευτέρα

      • Derandomization of Complexity Classes: Uniform Derandomization, consequences to Circuit Lower Bounds.
      • Παρουσιάσεις φοιτητών.


      Πέμπτη

      • Derandomization of Complexity Classes: The Easy Witness Lemma
      • Παρουσιάσεις φοιτητών.

    • Collapse Expand

      22 January - 28 January

      Δευτέρα

      • Παρουσιάσεις φοιτητών.


      Πέμπτη (αναβλήθηκε για 2/2/23, λόγω καιρικών συνθηκών)

      • Παρουσιάσεις φοιτητών.