Weekly outline

• General
  

  General

  Ακαδημαϊκό έτος 

  • 2019-2020 (εαρινό εξάμηνο)

  Διδάσκοντες

  • Στάθης Ζάχος
  • Πέτρος Ποτίκας (ppotik@cs.ntua.gr)
  • Γιάννης Κοκκίνης (ykokkinis@gmail.com)

  
  

  Βοηθός διδασκαλίας

  • Αγγελική Χαλκή (achalki@corelab.ntua.gr)

  
  

  Έναρξη μαθήματος

  • Τρίτη 25/2/2020, 11:00, αιθ. 1.1.31, παλ. κτ. ΗΜΜΥ

  
  

  Διαλέξεις

  • Κάθε Τρίτη 11:00-15:00, αιθ. 1.1.31, παλ. κτ. ΗΜΜΥ

  
  

  Περιγραφή μαθήματος

  Περιγραφική πολυπλοκότητα. Σύνδεση λογικής και κλάσεων πολυπλοκότητας.

  
  

  Προαπαιτούμενα

  • Τουλάχιστον ένα μάθημα Μαθηματικής Λογικής και ένα μάθημα Πολυπλοκότητας.

  
  

  Βιβλιογραφία

  • Neil Immerman. Descriptive Complexity
  • Leonid Libkin. Elements of Finite model theory
  • Christos H. Papadimitriou. Computational Complexity

  
  

  • Ανακοινώσεις Forum
  • Πρόγραμμα Παρουσιάσεων File
  • Το forum του μαθήματος

    Αν έχετε κάποια απορία για το μάθημα δημιουργείστε ένα θέμα συζήτησης εδώ. Στείλτε e-mail στους διδάσκοντες μόνο για προσωπικές απορίες.

• 25 February - 2 March
  

  25 February - 2 March

  • Preliminaries in Logic File
  • Immerman: (Parts from) Chapter 1
    
• 3 March - 9 March
  

  3 March - 9 March

  • • Immerman: Finished Chapter 1, Sections 2.1 and 2.2
    • Lemma 7.2 from "On uniformity within NC1"

• 10 March - 16 March
  

  10 March - 16 March

  • Complexity Preliminaries File
  • Ιmmerman: Chapter 2

  • Papadimitriou: Parts from Chapter 7

• 17 March - 23 March
  

  17 March - 23 March

  • No lecture

• 24 March - 30 March
  

  24 March - 30 March

  • First Order Reductions File
  • Immerman: Chapter 3

• 31 March - 6 April
  

  31 March - 6 April

  • Inductive Definitions File
  • Immerman: Chapter 4

  • Libkin: Parts from Chapter 10

• 7 April - 13 April
  

  7 April - 13 April

  • Ehrenfeucht Fraisse Games File
  • Libkin: Chapter 3

• 14 April - 20 April
  

  14 April - 20 April

  • Locality and Winning Games File
  • Libkin: Chapter 4

• 21 April - 27 April
  

  21 April - 27 April

  • No Lecture (Easter Holidays)

• 28 April - 4 May
  

  28 April - 4 May

  • Parallelism and Circuit Complexity File
  • Immerman: Chapter 5

• 5 May - 11 May
  

  5 May - 11 May

  • Complexity of First Order Logic File
  • Libkin: Chapter 6

• 12 May - 18 May
  

  12 May - 18 May

  • SO Logic and Lower Bounds File
  • Immerman: Chapter 8

• 19 May - 25 May
  

  19 May - 25 May

  • Fagin's Theorem, SO Logic and Trakhtenbrot's Theorem File
  • Immermann: Chapter 7
    Libkin: Chapter 9

• 26 May - 1 June
  

  26 May - 1 June

  • Dynamic Complexity: A Brief Introduction File
  • Immerman: Section 14.2

    DynFO A Parallel, Dynamic Complexity Class

• 2 June - 8 June
  

  2 June - 8 June

  • Finite Variable Logics File

    Libkin: Chapter 11

• 9 June - 15 June
  

  9 June - 15 June

  • MSO and Automara File

    Libkin: Chapter 7

• 16 June - 22 June
  

  16 June - 22 June

  • Descriptive Complexity for Counting Classes File