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.



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


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

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

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


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

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

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

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

                              • 20 December - 26 December

                                Δευτέρα

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

                                • 10 January - 16 January

                                  Δευτέρα

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

                                    Πέμπτη

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

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