Δομική Πολυπλοκότητα
Weekly outline
- Χειμερινό Εξάμηνο 2022-2023
Χειμερινό Εξάμηνο 2022-2023
Προσφέρεται ως "Υπολογιστική Πολυπλοκότητα" στην ΣΗΜΜΥ.
Διδάσκοντες:
- Στάθης Ζάχος, Καθηγητής (zachos@cs.ntua.gr)
- Άρης Παγουρτζής, Καθηγητής (pagour@cs.ntua.gr)
Βοηθοί Διδασκαλίας:
- Αντώνης Αντωνόπουλος, Υ/Δ (aanton@corelab.ntua.gr)
- Σταύρος Πετσαλάκης, Υ/Δ (spetsalakis@corelab.ntua.gr)
Διαλέξεις:
- Δευτέρα 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. - 2 October - 8 October
- 9 October - 15 October
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]
- 16 October - 22 October
16 October - 22 October
Δευτέρα 17 Οκτωβρίου
- Guest Lecture: Kakutani Fixed Point Theorem, Concave Games and PPAD (Emmanouil Vasileios Vlatakis Gkaragkounis)
Πέμπτη 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]
Δείτε επίσης: - Guest Lecture: Kakutani Fixed Point Theorem, Concave Games and PPAD (Emmanouil Vasileios Vlatakis Gkaragkounis)
- 23 October - 29 October
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.
Πέμπτη
Δεν έγινε μάθημα. - Basic notions and results of Complexity Theory: Reductions and completeness, space complexity basics. Overview of deterministic and nondeterministic time and space classes.
- 30 October - 5 November
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]
- 6 November - 12 November
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]
- Oracles & The Polynomial Hierarchy: The polynomial-time hierarchy and related theorems.
- 13 November - 19 November
13 November - 19 November
Δευτέρα
- The Structure of NP: Padding, NP-isomorphism, The “Berman-Hartmanis” conjecture, density, sparse sets.
Πέμπτη
Δεν έγινε μάθημα. - 20 November - 26 November
20 November - 26 November
Δευτέρα
- The Structure of NP: Mahaney's Theorem.
Πέμπτη
- Randomized Computation: Probabilistic Turing machines, the classes BPP, RP, coRP and ZPP.
- 27 November - 3 December
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]
- 4 December - 10 December
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]
- Non-Uniform Complexity: Circuit Complexity review, Algorithms for Circuit Analysis.
- 11 December - 17 December
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)Thinking Algorithmically About Impossibility (Ryan Williams) - Circuit
Lower Bounds: Håstad’s Switching Lemma and applications to
lower bounds for parity, oracle worlds, computational learning and
decision tree complexity.
- 18 December - 24 December
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]
- Interactive Proofs: Deterministic verifiers, probabilistic verifiers and the class IP, public and private coins, Arthur-Merlin Games, the class AM and its properties.
- 8 January - 14 January
8 January - 14 January
Δευτέρα
- Αντί μαθήματος, παρακολούθηση σειράς ομιλιών.
Πέμπτη
- Derandomization of Complexity Classes: The Nisan-Wigderson Construction, Worst-case and average case hardness.
- Παρουσιάσεις φοιτητών.
- Αντί μαθήματος, παρακολούθηση σειράς ομιλιών.
- 15 January - 21 January
15 January - 21 January
Δευτέρα
- Derandomization of Complexity Classes: Uniform Derandomization, consequences to Circuit Lower Bounds.
- Παρουσιάσεις φοιτητών.
Πέμπτη
- Derandomization of Complexity Classes: The Easy Witness Lemma
- Παρουσιάσεις φοιτητών.
- 22 January - 28 January
22 January - 28 January
Δευτέρα
- Παρουσιάσεις φοιτητών.
Πέμπτη (αναβλήθηκε για 2/2/23, λόγω καιρικών συνθηκών)
- Παρουσιάσεις φοιτητών.