Υπολογιστική Πολυπλοκότητα
Weekly outline
- Χειμερινό Εξάμηνο 2016-2017
Χειμερινό Εξάμηνο 2016-2017
Προσφέρεται ως "Θεωρητική Πληροφορική Ι: Αλγόριθμοι και Πολυπλοκότητα" στην ΣΗΜΜΥ, και ως "Αλγόριθμοι και Πολυπλοκότητα ΙΙ" στο ΜΠΛΑ.
Διδάσκοντες:
- Στάθης Ζάχος, Καθηγητής (zachos@cs.ntua.gr)
- Άρης Παγουρτζής, επ. Καθηγητής (pagour@cs.ntua.gr)
Βοηθοί Διδασκαλίας:
- Αντώνης Αντωνόπουλος, Υ/Δ (aanton@corelab.ntua.gr)
- Αγγελική Χαλκή, Υ/Δ (achalki@corelab.ntua.gr)
Διαλέξεις:
- Δευτέρα 17:00-18:30 (Παλιά Κτίρια Ηλεκτρολόγων ΕΜΠ, Αίθουσα 1.1.31)
- Πέμπτη 15:00-17:00 (Παλιά Κτίρια Ηλεκτρολόγων ΕΜΠ, Αίθουσα 1.1.31)
Έναρξη: Δευτέρα, 10 Οκτωβρίου 2016
Ώρες Γραφείου:
- ΤΒΑ
- 10 October - 16 October
10 October - 16 October
ΔΕΥΤΕΡΑ
- Διοικητικά - Διαδικαστικά
- Hierarchies of Complexity Classes (Course overview)
- Introduction to Complexity Theory.
- Problems, Algorithms and Languages. Decision and optimization problems.
- Turing machines with multiple strings, linear speedup, nondeterminism.
- Equivalence of Computational Models, Turing Machines, Representation as strings.
- Computability & Undecidability: The Universal Turing Machine, Simulation, Diagonalization
ΠΕΜΠΤΗ
- Introduction to Complexity Theory.
- Problems, Algorithms and Languages. Decision and optimization problems.
- 17 October - 23 October
17 October - 23 October
ΔΕΥΤΕΡΑ
- Turing machines with multiple strings, linear speedup, nondeterminism.
- Equivalence of Computational Models, Turing Machines, Representation as strings.
- Computability & Undecidability: The Universal Turing Machine, Simulation, Diagonalization
ΠΕΜΠΤΗ
- Complexity Classes: Complexity Measures, Time and Space Classes, Hierarchy Theorems, Gap Theorem.
Προτεινόμενη Μελέτη:
-Ch.1,2 από το [1]
-Ch.3: p. 57-63 από τo [1]
-Ch. 7: p.139-146 από το [1]
- Ch.1 από το [2] - 24 October - 30 October
24 October - 30 October
ΔΕΥΤΕΡΑ
- Space Computation: The classes L and NL, Savitch's Theorem, NL-completeness
ΠΕΜΠΤΗ
- Space Computation: Immerman-Szelepscényi Theorem
Προτεινόμενη Μελέτη:
- Ch.7: p. 146-153 από το [1]
-Ch.4 από το [2] - 31 October - 6 November
31 October - 6 November
ΔΕΥΤΕΡΑ
- Oracles, Oracle Turing Machines and Oracle Classes, Relativizations, The Limits of Diagonalization.
ΠΕΜΠΤΗ
- The Polynomial Hierarchy: Definition, Main Properties, Collapsion and consequences.
Προτεινόμενη Μελέτη:
-Ch. 14: Section 14.3 από το [1]
- Ch. 17: Section 17.2 από το [1]
- Ch.3: Section 3.4 από το [2] - 7 November - 13 November
7 November - 13 November
ΔΕΥΤΕΡΑ
- Reductions & Completeness: Different types of reductions and relations among them.
ΠΕΜΠΤΗ
- Reductions & Completeness: completeness, closure under reductions.
Προτεινόμενη Μελέτη:
-Ch.8,9 από το [1] - Reductions & Completeness: Different types of reductions and relations among them.
- 14 November - 20 November
14 November - 20 November
ΔΕΥΤΕΡΑ
- Reductions & Completeness: NP-completeness.
ΠΕΜΠΤΗ
- Reductions & Completeness: Cook's Theorem.
Προτεινόμενη Μελέτη:
-Ch.8,9 από το [1] - Reductions & Completeness: NP-completeness.
- 21 November - 27 November
21 November - 27 November
ΔΕΥΤΕΡΑ
- Randomized Computation: The classes BPP, RP, coRP
ΠΕΜΠΤΗ
- Randomized Computation: The classes ZPP, RP, coRP, and relations among them, Quantifier Notation ane related results, The BPP-Theorem, the "P vs BPP Question".
Προτεινόμενη Μελέτη:
- Ch 7: Sections 7.1,7.2 από το [2]
- Section 1 από εδώ.
- 28 November - 4 December
28 November - 4 December
ΔΕΥΤΕΡΑ- Randomized Computation: Syntactic and semantic classes, Error Reduction, The Class PP, Relativized Results.
ΠΕΜΠΤΗ
- Non-Uniform Complexity: Boolean Circuits, the class P/poly, Advice Turing Machines
Προτεινόμενη Μελέτη:
- Ch 7: Sections 7.1,7.2 από το [2]
- Section 1 από εδώ.
- Ch 6: Sections 6.1-6.5 από το [2]
- 5 December - 11 December
5 December - 11 December
ΔΕΥΤΕΡΑ
- Non-Uniform Complexity: Circuit Lower Bounds, Natural Proofs
ΠΕΜΠΤΗ
- Interactive Proofs: Deterministic verifiers, probabilistic verifiers and the class IP, Public and private coins, Arthur-Merlin Games
Προτεινόμενη Μελέτη:
- Ch 6: Sections 6.1-6.5 από το [2]
- Ch 8: Section 8.1, 8.2 από το [2]
- Non-Uniform Complexity: Circuit Lower Bounds, Natural Proofs
- 9 January - 15 January
9 January - 15 January
ΔΕΥΤΕΡΑ
- Interactive Proofs: The Class AM, Quantifier Notation, Perfect Completeness for AM
ΠΕΜΠΤΗ
- Interactive Proofs: Collapsion of AM[k] hierarchy to AM=AM[2], Relativized results
Προτεινόμενη Μελέτη:
- Ch 8: Sections 8.1-8.2 από το [2]
- Section 2 από εδώ.
- Interactive Proofs: The Class AM, Quantifier Notation, Perfect Completeness for AM
- 16 January - 22 January
16 January - 22 January
ΔΕΥΤΕΡΑ
- Interactive Proofs: Shamir's Theorem (IP=PSPACE)
ΠΕΜΠΤΗ
- Counting Complexity: Counting vs Decision Problems, the class #P, #SAT, PERMANENT, Parsimonious, Cook and Cook[1] (metric) reductions for Counting Problems, Valiant-Vazirani Theorem
Προτεινόμενη Μελέτη:
- Ch 8: Section 8.3 από το [2]
- Chapter 18 από το [1].
- 23 January - 29 January
23 January - 29 January
ΔΕΥΤΕΡΑ
- Interactive Proofs: Quantifiers vs Counting: Toda's Theorem.
Προτεινόμενη Μελέτη:
- Chapter 18 από το [1].
- Interactive Proofs: Quantifiers vs Counting: Toda's Theorem.
- 6 February - 12 February
6 February - 12 February
ΔΕΥΤΕΡΑ 6 ΦΕΒΡΟΥΑΡΙΟΥ
Ομιλίες Φοιτητών (1/2):
- Average-Case Complexity (Αλέξανδρος Ζαχαράκης)
- Pseudorandomness (Πλάτων Παπαδόπουλος)
- Communication Complexity (Ιωσήφ Μουλίνος)
- 27 February - 5 March
27 February - 5 March
ΤΕΤΑΡΤΗ 1 ΜΑΡΤΙΟΥ
Ομιλίες Φοιτητών (2/2):
- Quantum Computation (Γιώργος Πιτσιλαδής)
- Function Problems (Ανθή Κορρέ)
- Zero-Knowledge Proofs (Κατερίνα Νικλάνοβιτς)
- Proof Complexity (Αριστοτέλης Χανιώτης)
- PCPs and Inapproximability (Παναγιώτης Πατσιλινάκος)
- Alternation (Νίκος Καραγιάννης-Αξυπολιτίδης)