Αλγόριθμοι και Πολυπλοκότητα ΙΙ (ΜΠΛΑ)
Section outline
-
ΔΕΥΤΕΡΑ
- Ιστορική Εισαγωγή: 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)
-
ΔΕΥΤΕΡΑ
- 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
-
ΔΕΥΤΕΡΑ
- 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]
-
ΔΕΥΤΕΡΑ
- Θ. Λιανέας (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
-
ΔΕΥΤΕΡΑ
-
Ομιλίες φοιτητών:
- Ι. Λιβιεράτος: 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]
-
-
ΔΕΥΤΕΡΑ
Αργία
ΠΕΜΠΤΗ
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
- Ομιλίες φοιτητών:
-
ΔΕΥΤΕΡΑ
- Ομιλίες φοιτητών:
- Κ. Ζαμπετάκης (συν.): Mahaney's Theorem
- Ν. Κωτσάνη (συν.): Fagin’s Theorem
ΠΕΜΠΤΗ
Δεν θα γίνει μάθημα λόγω απεργίας!
- Ομιλίες φοιτητών:
-
ΔΕΥΤΕΡΑ
- Ομιλίες Φοιτητών:
- Σ. Σκουλάκης: 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 από εδώ.
- Ομιλίες Φοιτητών:
-
ΔΕΥΤΕΡΑ
- 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]
-
ΔΕΥΤΕΡΑ
- 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]
-
ΔΕΥΤΕΡΑ
- Μανώλης Ζαμπετάκης (ΜΙΤ): Dinur's Proof of the PCP Theorem
-
ΠΕΜΠΤΗ
- Oracles & Optimization Problems
- The Polynomial Hierarchy
-
ΔΕΥΤΕΡΑ
- 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
-
ΔΕΥΤΕΡΑ
- 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
-
ΔΕΥΤΕΡΑ
- Ομιλίες φοιτητών:
Χ. Τζόβας: Algebraic Computation
Λ. Ζακυνθινού: PCPs & Inapproximability
ΠΕΜΠΤΗ
- 2o Quiz
- Toda's Theorem
- Ομιλίες φοιτητών:
-
ΔΕΥΤΕΡΑ
- Ομιλίες φοιτητών:
Μ. Σάμαρης: Average-Case Complexity
Δ. Τσίπρας: Fourier Analysis & Inapproximability
ΠΕΜΠΤΗ
- Ομιλίες φοιτητών:
Ο. Κωνσταντινίδης & Μ. Κουβαράς: Quantum Computation
- Ομιλίες φοιτητών: