Section outline

  • Collapse Expand

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

    Collapse all Expand all

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

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

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

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


    Περιεχόμενο Μαθήματος:
    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

    Εβδομάδα 1

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

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

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

    • Basic notions and results of Complexity Theory: Complexity Measures, Complexity Classes, Hierarchy Theorems. 


    Μπορείτε να διαβάσετε:

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

  • Collapse Expand

    Εβδομάδα 2

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

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


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

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


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




  • Collapse Expand

    Εβδομάδα 3

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

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


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

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

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


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

  • Collapse Expand

    Εβδομάδα 4

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

    • Oracles & The Polynomial Hierarchy: The complexity of optimization problems, the class FPNP.
    • The Structure of NP: Enumerations, Ladner’s Theorem, Padding, NP-isomorphism, The “Berman-Hartmanis” conjecture.


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

    • The Structure of NP: Proof of Ladner’s Theorem, Padding, Density, Sparse Sets.

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

  • Collapse Expand

    Εβδομάδα 5

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

    • The Structure of NP: Mahaney's Theorem.

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


    Πέμπτη 2 Νοεμβρίου

    • Randomized Computation: Quantifier notation and related results, the the class ZPP, semantic and syntactic classes, the “P vs BPP” question.


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

  • Collapse Expand

    Εβδομάδα 6

    Δευτέρα 6 Νοεμβρίου

    • Randomized Computation: Semantic and syntactic classes, the “P vs BPP” question, Relativized Results.


    Πέμπτη 9 Νοεμβρίου

    • Non-Uniform Complexity: Boolean circuits, the class P/poly and related results, Turing Machines with advice, Karp-Lipton Theorem.


    Μπορείτε να διαβάσετε:

    • Sections 7.1-7.5 from [2]
    • Sections 6.1-6.7 from [2]



  • Collapse Expand

    Εβδομάδα 7

    Δευτέρα 13 Νοεμβρίου

    • Non-Uniform Complexity: Circuit Complexity review, Algorithms for Circuit Analysis. Boolean Functions, Circuit Lower Bounds, Kannan's Lower Bound.


    Πέμπτη 16 Νοεμβρίου

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


  • Collapse Expand

    Εβδομάδα 8

    Δευτέρα 20 Νοεμβρίου

    • Non-Uniform Complexity: Circuit Classes, Uniform circuit families and parallel computations. 


    Πέμπτη 23 Νοεμβρίου

    • Non-Uniform Complexity: Håstad’s Switching Lemma and applications to lower bounds for parity, oracle worlds, computational learning and decision tree complexity. The polynomial approximation method.


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

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

    The Switching Lemma (Ryan O' Donnell)




  • Collapse Expand

    Εβδομάδα 9

    Δευτέρα 27 Νοεμβρίου

    • Non-Uniform Complexity: Lower bounds for ACC0, lower bounds from algorithms (NEXP vs ACC0), Algorithms from lower bounds techniques. Monotone functions and circuit lower bounds. Natural proofs: the Circuit Complexity Barrier.


    Πέμπτη 30 Νοεμβρίου

    • Interactive Proofs: Deterministic verifiers, probabilistic verifiers and the class IP, public and private coins, Arthur-Merlin Games, the class AM and its properties

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