Μάθημα: Αλγόριθμοι και Πολυπλοκότητα ΙΙ (ΜΠΛΑ)

Περιγραφή εβδομάδας

17 November - 23 November

ΔΕΥΤΕΡΑ

ΠΕΜΠΤΗ

Χειμερινό Εξάμηνο 2014-2015
Χειμερινό Εξάμηνο 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]
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]
- Reductions and NP-Completeness (Α. Χαλκή) Αρχείο
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]
- NP-complete problems (Ι. Λιβιεράτος) Αρχείο
- Ladner’s Theorem, Sparse and Dense Languages (Β. Βελώνα) Αρχείο

Αργία

Σήμερα Thursday, 21 November 21

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

The "Berman-Hartmanis" Conjecture, NP-isomorphism, padding, 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 από εδώ.
- NP, coNP and Function Problems (Σ. Σκουλάκης) Αρχείο
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
22 December - 28 December
ΔΕΥΤΕΡΑ
- Μανώλης Ζαμπετάκης (ΜΙΤ): Dinur's Proof of the PCP Theorem
- Dinur's Proof of the PCP THeorem (Μ. Ζαμπετάκης) Αρχείο
29 December - 4 January δεν είναι διαθέσιμο
5 January - 11 January
5 January - 11 January
ΠΕΜΠΤΗ
- Oracles & Optimization Problems
- The Polynomial Hierarchy
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
ΠΕΜΠΤΗ
- 2^o Quiz
- Toda's Theorem
- Algebraic Computation (Χ. Τζόβας) Αρχείο
- PCPs and Inapproximability (Λ. Ζακυνθινού) Αρχείο
2 February - 8 February
2 February - 8 February
ΔΕΥΤΕΡΑ
- Ομιλίες φοιτητών:
  Μ. Σάμαρης: Average-Case Complexity
  Δ. Τσίπρας: Fourier Analysis & Inapproximability
ΠΕΜΠΤΗ
- Ομιλίες φοιτητών:
  Ο. Κωνσταντινίδης & Μ. Κουβαράς: Quantum Computation