Font size: Αα Αα Αα hide gadgets
You are here: Courses » 2012-2013 » fall semester » Λ4. Algorithms and complexity II (2012-2013, fall semester)

Algorithms and complexity II: 2012-2013, fall semester

This is a course that has been given 18 times. For information about this course in general (not just for this specific semester), visit its page: Λ4. Algorithms and complexity II.

Taught by: Aristeidis T. Pagourtzis & Efstathios Zachos
Teaching assistant: Antonis Antonopoulos
Start date: Oct. 8, 2012
End date:

Teaching hours

  • every Monday, 17:00-19:00, 1.1.29, ece, NTUA (old buildings)
  • every Thursday, 13:45-15:45, 1.1.29, ece, NTUA (old buildings)

Course information

Ώρες γραφείου: Παρασκευή 12:00-16:00, στο Eργαστήριο Λογικής και Επιστήμης Υπολογισμών (CoReLab), Αίθουσα 1.1.3, Παλιά Κτίρια ΗΜΜΥ, ΕΜΠ.

Φυλλάδιο Μαθήματος-Syllabus

(Εξεταστέα) ύλη μαθήματος

Για τακτικές ενημερώσεις και πληροφορίες σχετικά με το μάθημα, παρακαλώ δείτε την σελίδα του μαθήματος εδώ. Το παρακάτω προφίλ του μαθήματος θα συγχρονίζεται με την σελίδα περιοδικά.

Enrolled students



Monday, 08 Oct 2012 Zachos

Εισαγωγή - Διαδικαστικά Hierarchies of Complexity Classes

Thursday, 11 Oct 2012 Zachos

Computational Models, Hierarchies, History

Monday, 15 Oct 2012 Zachos

Computational Model-Turing Machines: Equivalence of Computational Models, Turing Machines, Time and Space bounds, multiple strings, linear speedup, nondeterminism.

Thursday, 18 Oct 2012 Zachos

Computability and Undecidability: The Universal Turing Machine, Simulation, Diagonalization, The Halting Problem, Recursive and Recursive Enumerable Sets.

Monday, 22 Oct 2012 Antonopoulos

Complexity Classes: Complexity measures, Time and Space Classes Hierarchy Theorems, Gap Theorem, Basic inclusions between complexity classes, Quantifier Notation and characterization of NP (Theorem 9.1 [1]).

Monday, 29 Oct 2012 Zachos

Space Computation: The classes L and NL, Savitch’s Theorem, Immerman-Szelepscényi Theorem (NL=coNL), Reingold’s Theorem: L=SL (without proof) & Undirected REACHABILITY.

Thursday, 01 Nov 2012 Zachos

Second-Order Logic, Incompleteness, Fagin's Theorem

Monday, 05 Nov 2012 Zachos

Second-Order Logic, Incompleteness, Fagin's Theorem (cont'd)

Thursday, 08 Nov 2012 Zachos

Second-Order Logic, Incompleteness, Fagin's Theorem (cont'd). The Arithmetical Hierarchy.

Monday, 12 Nov 2012 Zachos

Diagonalization & Hierarchies, Case-Study: DTIME(n)⊂DTIME(n^1.5) Reductions: Reductions between problems, P-completeness, NP-completeness.

Monday, 19 Nov 2012 Zachos

Reductions: Different types of reductions (Karp, Cook, Cook[1], tt), and relations among them. NP-Complete Problems: - Cook’s Theorem, SAT and satisfiability variants - IS,CLIQUE, MAX-CUT

Thursday, 22 Nov 2012 Zachos

NP-Complete Problems: - HP, TSP, 3COL, 0/1 IP - 3DM, KNAPSACK, Pseudopolynomial Algorithms and Strong NP-Completeness

Monday, 26 Nov 2012 Zachos

Ladner’s Theorem, Density, Sparse sets The “Berman-Hartmanis” conjecture, NP-isomorphism, padding.

Thursday, 29 Nov 2012 Zachos

Function Problems: The classes coNP and ∆NP, Function classes (FL, FP, FNP, FPSPACE etc) and reductions, the classes PLS and PPAD.

Monday, 03 Dec 2012 Zachos

Randomized Computation: Randomized Algorithms, BPP, RP, coRP, ZPP classes.

Thursday, 06 Dec 2012 Zachos

Oracles & The Polynomial Hierarchy: Oracles and oracle classes, the Polynomial-Time Hierarchy.

Thursday, 13 Dec 2012 Zachos

Quantifier notation (∃+) and related results, semantic and syntactic classes, the “P vs BPP” question.

Monday, 17 Dec 2012 Zachos

2o Quiz σε Reductions & Randomized Complexity Classes. The equivalence between Oracle and Quantifier Polynomial Hierarchy

Thursday, 20 Dec 2012 Zachos

The Polynomial-Time Hierarchy and related theorems, The BPP Theorem, Swapping quantifiers, Operator-defined classes.

Thursday, 10 Jan 2013 Zachos

Non-Uniform Complexity: Boolean circuits, the class P/poly, Advice Turing Machines, Circuit Lower Bounds, Natural Proofs.

Monday, 14 Jan 2013 Zachos

Parallel computation (classes NC, RNC, AC, TC)

Interactive Proof Systems:

-Interactive Proofs (IP)

Thursday, 17 Jan 2013 Zachos

Interactive Proof Systems:

-Arthur-Merlin Games (AM)

Monday, 21 Jan 2013 Zachos

Interactive Proof Systems:

-Shamir’s Theorem: IP=PSPACE

-Zero Knowledge Proofs

Thursday, 24 Jan 2013 Zachos

Quantifier Notation and Arthur-Merlin Games

An introduction to Pseudorandomness and Derandomization

Introduction to PCPs

Monday, 28 Jan 2013 Zachos

Interactive Proof Systems:

-Probabilistically Checkable Proofs (PCP)

-Dinur's Proof of the PCP Theorem

Thursday, 31 Jan 2013 Zachos

Counting Complexity: #P, #P-completeness, Toda's Theorem, Gaps

Approximability and Approximation Schemes

Monday, 04 Feb 2013 Zachos

Reingold's Theorem: L=SL

Quantum Computation

Thursday, 07 Feb 2013 Zachos


Interactive Proof Systems: -Hardness of Approximations

Pseudorandomness & Combinatorial Constructions

The Unique Games Conjecture

Monday, 11 Feb 2013 Zachos

Algebraic Computation

The Bright Side of Hardness


# handout given on deadline solutions
1 1η Σειρά Ασκήσεων Monday, 29 Oct 2012 2012-11-29
2 2η Σειρά Ασκήσεων Sunday, 30 Dec 2012 2013-01-24
3 3η Σειρά Ασκήσεων Friday, 08 Feb 2013 2013-03-10


You must be logged in to comment.


Web standards: XHTML1.0, CSS3.
© 1996 – 2018 MPLA: Graduate program in Logic, Algorithms and Computation.
Contact the webmaster.