Αλγόριθμοι και Πολυπλοκότητα ΙΙ (ΜΠΛΑ)
Weekly outline
- Χειμερινό Εξάμηνο 2014-2015
- 13 October - 19 October
13 October - 19 October
ΔΕΥΤΕΡΑ
- Ιστορική Εισαγωγή: Hierarchies of Complexity Classes
- Διοικητικά - Διαδικαστικά
ΠΕΜΠΤΗ
- 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.
Προτεινόμενο Διάβασμα:
- p. 3-26 από το [1]
Μπορείτε να δείτε επίσης:
- Invitation to complexity theory, Oded Goldreich (link)
- 20 October - 26 October
20 October - 26 October
ΔΕΥΤΕΡΑ
- Computability & Undecidability: The Universal Turing Machine, Simulation, Diagonalization
The Halting Problem, Recursive and Rec. Enumerable sets, Rice's Theorem
Προτεινόμενο Διάβασμα:
- p. 57-63 από το [1].
ΠΕΜΠΤΗ
- Complexity Classes: Complexity Measures, Time and Space Classes, Hierarchy Theorems, Gap Theorem.
- Space Computation: The classes L and NL, Savitch's Theorem.
Προτεινόμενο Διάβασμα:
- p. 139-151 από το [1]
- Computability & Undecidability: The Universal Turing Machine, Simulation, Diagonalization
- 27 October - 2 November
27 October - 2 November
ΔΕΥΤΕΡΑ
- Space Computation: Immerman-Szelepscényi Theorem, NL-completeness
Προτεινόμενο Διάβασμα:
- p. 151-153 από το [1]
- Chapter 3 aπό το [2]
ΠΕΜΠΤΗ
- Reductions & NP-Completeness: Different types of reductions and relations among them, NP-completeness
Προτεινόμενο Διάβασμα:
- p. 159-172 από το [1]
- 3 November - 9 November
3 November - 9 November
ΔΕΥΤΕΡΑ
- Θ. Λιανέας (NTUA): Reingold's Theorem: Undirected Reachability in Logspace
- Ομιλίες φοιτητών:
- Θ. Παπαμακάριος: NP-complete Problems: Cook's Theorem, SAT and Satisfiability variants.
ΠΕΜΠΤΗ
- Ομιλίες φοιτητών:
- M. Πετροπαναγιωτάκη: NP-complete Problems: IS, CLIQUE, MAX-CUT
- Δ. Διαμαντής: NP-complete Problems: IS, CLIQUE, MAX-CUT
- 10 November - 16 November
10 November - 16 November
ΔΕΥΤΕΡΑ
-
Ομιλίες φοιτητών:
- Ι. Λιβιεράτος: NP-complete Problems: 3DM, Knapsack, Pseudopolynomial Algorithms and Strong NP-completeness
- Β. Βελώνα: Ladner's Theorem, Density, Sparse Sets
Προτεινόμενο Διάβασμα:
- Chapter 9 από το [1]
- Sections 14.1, 14.2 (p. 329-339) από το [1]
ΠΕΜΠΤΗ
- Ομιλίες φοιτητών:
- Κ. Ζαμπετάκης: The "Berman-Hartmanis" Conjecture, NP-isomorphism, padding
- Ν. Κωτσάνη: Second-Order Logic, Undecidability-Incompleteness, Fagin’s Theorem
Προτεινόμενο Διάβασμα:
- p. 173-176 από το [1]
-
- 17 November - 23 November
17 November - 23 November
ΔΕΥΤΕΡΑ
Αργία
ΠΕΜΠΤΗ
1ο Quiz
Ύλη:
- Το 1ο set διαφανειών του μαθήματος
- Από το βιβλίο του Παπαδημητρίου [1]:
-- Sections 2.1-2.5, 2.7
-- Chapter 3 (όχι σελ. 64,65)
-- Chapter 7
-- Section 8.1-8.2- Ομιλίες φοιτητών:
- Κ. Ζαμπετάκης (συν.): Mahaney's Theorem
- Ομιλίες φοιτητών:
- 24 November - 30 November
24 November - 30 November
ΔΕΥΤΕΡΑ
- Ομιλίες φοιτητών:
- Κ. Ζαμπετάκης (συν.): Mahaney's Theorem
- Ν. Κωτσάνη (συν.): Fagin’s Theorem
ΠΕΜΠΤΗ
Δεν θα γίνει μάθημα λόγω απεργίας!
- Ομιλίες φοιτητών:
- 1 December - 7 December
1 December - 7 December
ΔΕΥΤΕΡΑ
- Ομιλίες Φοιτητών:
- Σ. Σκουλάκης: Function Problems: The classes coNP and ΔNP, Function classes and reductions, the classes PLS and PPAD.
ΠΕΜΠΤΗ
- Randomized Computation: The classes BPP, RP, coRP, ZPP, Quantifier Notation ane related results, syntactic and semantic classes, The BPP-Theorem, the "P vs BPP Question".
Προτεινόμενο Διάβασμα:
- Sections 7.1-7.3 (p. 123-132) από το [2]
- Section 1 από εδώ.
- Ομιλίες Φοιτητών:
- 8 December - 14 December
8 December - 14 December
ΔΕΥΤΕΡΑ
- Randomized Computation: Error Reduction, The Class PP, Relativized Results
- Oracles and Oracle Classes. Relativizations.
Προτεινόμενο Διάβασμα:
- Sections 7.4, 7.5 (p. 132-138) από το [2]
- p. 256-257 (class PP) από το [1]
- Section 14.3 (p. 339-343) από το [1]
ΠΕΜΠΤΗ
- Interactive Proofs: Interactive Proof Systems, the class IP[k]
Προτεινόμενο Διάβασμα:
Section 8.1 από το [2]
- 15 December - 21 December
15 December - 21 December
ΔΕΥΤΕΡΑ
- Interactive Proofs: IPs, Arthur-Merlin Games, Quantifier Notation and related results
Προτεινόμενο Διάβασμα:
Section 8.2 από το [2]
Section 2 από εδώ.ΠΕΜΠΤΗ
- Shamir's Theorem
Προτεινόμενο Διάβασμα:
Section 8.3 από το [2]
- Probabilistically Checkable Proofs
Προτεινόμενο Διάβασμα:
Section 11.1, 11.2 από το [2]
- 22 December - 28 December
- 5 January - 11 January
- 12 January - 18 January
12 January - 18 January
ΔΕΥΤΕΡΑ
- Non-Uniform Complexity: Boolean Circuits, the class P/poly, Advice Turing Machines, Circuit Lower Bounds, Natural Proofs
ΠΕΜΠΤΗ
- Counting Complexity: The Class #P, #P-completeness & The Permanent, Other Counting Classes, Gaps
- 19 January - 25 January
19 January - 25 January
ΔΕΥΤΕΡΑ
- Counting Complexity: Counting problems with easy decision, the class #PE, the class TotP
ΠΕΜΠΤΗ
- Counting Complexity: Operators on Complexity Classes, Valiant-Vazirani Theorem, Toda's Theorem
- Ομιλίες φοιτητών:
Ι. Παπαϊωάννου: Zero-Knowledge Proofs
- 26 January - 1 February
26 January - 1 February
ΔΕΥΤΕΡΑ
- Ομιλίες φοιτητών:
Χ. Τζόβας: Algebraic Computation
Λ. Ζακυνθινού: PCPs & Inapproximability
ΠΕΜΠΤΗ
- 2o Quiz
- Toda's Theorem
- Ομιλίες φοιτητών:
- 2 February - 8 February
2 February - 8 February
ΔΕΥΤΕΡΑ
- Ομιλίες φοιτητών:
Μ. Σάμαρης: Average-Case Complexity
Δ. Τσίπρας: Fourier Analysis & Inapproximability
ΠΕΜΠΤΗ
- Ομιλίες φοιτητών:
Ο. Κωνσταντινίδης & Μ. Κουβαράς: Quantum Computation
- Ομιλίες φοιτητών: