Weekly outline

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

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

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

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

    Διαλέξεις:
    • Δευτέρα 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.

  • 11 October - 17 October

    Δευτέρα

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



    Πέμπτη

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



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

    • Ch.2,7 from [1]
    • 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]
      Δείτε επίσης:

      • 25 October - 31 October

        Δευτέρα

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

        Πέμπτη

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



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

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



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

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


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

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


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