Section outline

  • Collapse Expand

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

    Collapse all Expand all

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

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

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

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


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

    11 October - 17 October

    Δευτέρα

    • Διοικητικά - Διαδικαστικά
    • Περιεχόμενο Μαθήματος
    • Επανάληψη κλασσικών εννοιών και αποτελεσμάτων της Πολυπλοκότητας: Είδη υπολογιστικών προβλημάτων, Μοντέλα Υπολογισμού, οι βασικές κλάσεις πολυπλοκότητας και οι σχέσεις μεταξύ τους, θεωρήματα ιεραρχίας.



    Πέμπτη

    • Επανάληψη κλασσικών εννοιών και αποτελεσμάτων της Πολυπλοκότητας:
      Προσομοίωση και διαγωνιοποίηση, αναγωγές και πληρότητα. Χωρική Πολυπλοκότητα (θεώρημα Savitch, θεώρημα Immerman-Szelepscényi).



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

    • Ch.2,7 from [1]
  • Collapse Expand

    18 October - 24 October

    Δευτέρα

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

    Πέμπτη

    • Oracles & The Polynomial Hierarchy: The polynomial-time hierarchy and related theorems, the complexity of optimization problems.


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

  • Collapse Expand

    25 October - 31 October

    Δευτέρα

    • The Structure of NP: Enumerations, Ladner’s Theorem.

    Πέμπτη

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



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

  • Collapse Expand

    1 November - 7 November

    Δευτέρα

    • The Structure of NP: Padding, NP-isomorphism, The “Berman-Hartmanis” conjecture, density, sparse sets, Mahaney's Theorem.
    • Randomized Computation: Probabilistic Turing machines, the class BPP.

    Πέμπτη

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



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


  • Collapse Expand

    8 November - 14 November

    Δευτέρα

    • Non-Uniform Complexity: Boolean circuits, the class P/poly and related results, Turing Machines with advice, Karp-Lipton Theorem, Algorithms for Circuits, Parallel computation (classes NC, RNC, AC, TC).

    Πέμπτη

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


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

  • Collapse Expand

    15 November - 21 November

    Δευτέρα

    Δεν έγινε μάθημα (εορτασμός Πολυτεχνείου).


    Πέμπτη

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

  • Collapse Expand

    22 November - 28 November

    Δευτέρα

      • Interactive Proofs: Shamir's Theorem (IP=PSPACE), Probabilistically Checkable Proofs, The Class PCP[r(n),q(n)].


      Πέμπτη

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

    • Collapse Expand

      29 November - 5 December

      Δευτέρα

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


        Πέμπτη

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


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

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

      • Collapse Expand

        6 December - 12 December

        Δευτέρα

          • Derandomization of Complexity Classes: The Nisan-Wigderson Construction, Worst-case and average case hardness


          Πέμπτη

          • Derandomization of Complexity Classes: Uniform Derandomization, consequences to Circuit Lower Bounds.


          Μπορείτε να διαβάσετε:
          • Section 20.1, 20.2 from [2]

        • Collapse Expand

          13 December - 19 December

          Δευτέρα

            • Derandomization of Complexity Classes: The Easy Witness Lemma Proof (1/2)

            Πέμπτη

            • Derandomization of Complexity Classes: The Easy Witness Lemma Proof (2/2)


            Μπορείτε να διαβάσετε:
            • Section 20.3, 20.4 from [2]

          • Collapse Expand

            20 December - 26 December

            Δευτέρα

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

          • Collapse Expand

            10 January - 16 January

            Δευτέρα

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

              Πέμπτη

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

            • Collapse Expand

              17 January - 23 January

              Δευτέρα

                • Παρουσιάσεις φοιτητών
                • Counting Complexity: The class #P, parsimonious reductions, completeness results, the class ⊕P,  Valiant-Vazirani Lemma, Toda's Theorem, the class GapP and applications.

                Μπορείτε να διαβάσετε:
                • Chapter 18 from [1]