Weekly outline

• Χειμερινό Εξάμηνο 2022-2023
  

  Χειμερινό Εξάμηνο 2022-2023

  Προσφέρεται ως "Υπολογιστική Πολυπλοκότητα" στην ΣΗΜΜΥ.
  

  Διδάσκοντες:

  • Στάθης Ζάχος, Καθηγητής (zachos@cs.ntua.gr)
  • Άρης Παγουρτζής, Καθηγητής (pagour@cs.ntua.gr)

  
  

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

  • Αντώνης Αντωνόπουλος, Υ/Δ (aanton@corelab.ntua.gr)
  • Σταύρος Πετσαλάκης, Υ/Δ (spetsalakis@corelab.ntua.gr)

  
  

  Διαλέξεις:

  • Δευτέρα 17:00-20:00 (Παλιά Κτίρια Ηλεκτρολόγων ΕΜΠ, Αίθουσα 1.1.31)
  • Πέμπτη 15:00-17:00 (Παλιά Κτίρια Ηλεκτρολόγων ΕΜΠ, Αίθουσα 1.1.31)
    

       Έναρξη μαθημάτων: 6/10/22

  
  

  
  

  Περιεχόμενο Μαθήματος:

  Basic notions and results in Complexity Theory. Oracles & The Polynomial Hierarchy. The structure of NP. Randomized Computation. Non-Uniform Complexity. Circuit Lower Bounds. Interactive Proofs. Probabilistically Checkable Proofs. Pseudorandomness and Derandomization of Complexity Classes. Circuit Lower Bounds for NEXP. Counting Complexity. A short introduction to Fine-Grained Complexity.
  

  
  

  • Ανακοινώσεις Forum
  • Βιβλιογραφία - Υλικό - Σύνδεσμοι Page
  • Διαθέσιμες Ομιλίες - Available Presentation Topics Page
  • Lecture Slides Folder
  • Lecture Notes (Draft Versions) Folder
  • 1η Σειρά Ασκήσεων File
  • Δήλωση Θέματος Παρουσίασης Choice
  • Επιλογή ημέρας παρουσίασης Choice
  • Υποβολή Σειράς Ασκήσεων Assignment
• 2 October - 8 October
  

  2 October - 8 October

  Πέμπτη 6 Οκτωβρίου
  

  • Συνάντηση γνωριμίας

  • Περιεχόμενο Μαθήματος
• 9 October - 15 October
  

  9 October - 15 October

  Δευτέρα 10 Οκτωβρίου

  • Basic notions and results of Complexity Theory: Problems, Turing Machines and their properties, Undecidability and Rice's Theorem

  
  

  Μπορείτε να διαβάσετε:
  

  • Ch. 1,2,3 from [1]
  • Ch. 0,1 from [2]
    

  Δείτε επίσης:
  

  • Στην υποσελίδα "Βιβλιογραφία-Υλικό-Σύνδεσμοι" θα βρείτε τις αναφορές για την βιβλιογραφία ([1], [2]), άλλες πηγές και σημειώσεις διαλέξεων, online courses Πολυπλοκότητας και άλλο ενδιαφέρον υλικό.

  
  

  
  

  Πέμπτη 13 Οκτωβρίου

  • Basic notions and results of Complexity Theory: Complexity Measures, Complexity Classes, Hierarchy Theorems. Separating complexity classes via diagonalization, proving inclusion of complexity classes via simulation.
    

  
  

  Μπορείτε να διαβάσετε:
  

  • Ch. 7 from [1]
  • Ch. 1,2,3 from [2]
    
• 16 October - 22 October
  

  16 October - 22 October

  Δευτέρα 17 Οκτωβρίου
  

  • Guest Lecture: Kakutani Fixed Point Theorem, Concave Games and PPAD (Emmanouil Vasileios Vlatakis Gkaragkounis)
    

  
  

  Πέμπτη 20 Οκτωβρίου

  • Basic notions and results of Complexity Theory: Certificate Characterization of NP, Efficient verification. Space Complexity (main results). Reductions.
    

  
  

  Μπορείτε να διαβάσετε:
  

  • Ch. 7 from [1]
  • Ch. 1,2,3 from [2]

  Δείτε επίσης:

  • Landscape of Computational Complexity Poster
    

  
  
• 23 October - 29 October
  

  23 October - 29 October

  Δευτέρα

  • Basic notions and results of Complexity Theory: Reductions and completeness, space complexity basics. Overview of deterministic and nondeterministic time and space classes.
    

  
  

  Πέμπτη

  Δεν έγινε μάθημα.
  

  
  
• 30 October - 5 November
  

  30 October - 5 November

  Δευτέρα

  • Oracles & The Polynomial Hierarchy: Oracles and oracle classes, Oracle worlds.

  
  

  Πέμπτη

  • Oracles & The Polynomial Hierarchy: The polynomial-time hierarchy and related theorems.

  
  

  
  

  Μπορείτε να διαβάσετε:

  • Section 14.3 from [1]
    
  • Ch. 17 from [1]
• 6 November - 12 November
  

  6 November - 12 November

  Δευτέρα

  • Oracles & The Polynomial Hierarchy: The polynomial-time hierarchy and related theorems.
    

  
  

  Μπορείτε να διαβάσετε:

  • Section 14.3 from [1]
    
  • Ch. 17 from [1]

  
  

  Δείτε επίσης:

  • List of complete problems in the Polynomial-Time Hierarchy

  
  

  Πέμπτη

  • Oracles & The Polynomial Hierarchy: The complexity of optimization problems, the class FP^NP.

  • The Structure of NP: Enumerations, Ladner’s Theorem.

  
  

  Μπορείτε να διαβάσετε:

  • Sections 14.1-14.2 from [1]

  
  

  
  
• 13 November - 19 November
  

  13 November - 19 November

  Δευτέρα

  • The Structure of NP: Padding, NP-isomorphism, The “Berman-Hartmanis” conjecture, density, sparse sets.

  
  

  Πέμπτη

  Δεν έγινε μάθημα.
  

  
  

  
  
• 20 November - 26 November
  

  20 November - 26 November

  Δευτέρα

  • The Structure of NP: Mahaney's Theorem.

  
  

  Πέμπτη

  • Randomized Computation: Probabilistic Turing machines, the classes BPP, RP, coRP and ZPP.
• 27 November - 3 December
  

  27 November - 3 December

  Δευτέρα

  • Randomized Computation: Quantifier notation and related results, semantic and syntactic classes, the “P vs BPP” question.
  • Non-Uniform Complexity: Boolean circuits, the class P/poly and related results, Turing Machines with advice, Karp-Lipton Theorem
    

  
  

  Πέμπτη

  • Non-Uniform Complexity: Uniform circuit families and parallel computations (S. Zachos)
    

  
  

  
  

  Μπορείτε να διαβάσετε:
  

  • Sections 7.1-7.5 from [2]

  
  
• 4 December - 10 December
  

  4 December - 10 December

  Δευτέρα

  • Non-Uniform Complexity: Circuit Complexity review, Algorithms for Circuit Analysis.
    

  
  

  Πέμπτη

  • Non-Uniform Complexity: Boolean Functions, Circuit Lower Bounds, Kannan's Lower Bound
    

  
  

  Μπορείτε να διαβάσετε:

  • Sections 6.1-6.7 from [2]
• 11 December - 17 December
  

  11 December - 17 December

  
  

  Δευτέρα

  • Circuit Lower Bounds: Håstad’s Switching Lemma and applications to lower bounds for parity, oracle worlds, computational learning and decision tree complexity.
    

  
  

  Πέμπτη

  • Circuit Lower Bounds: The polynomial approximation method, lower bounds for ACC⁰, lower bounds from algorithms (NEXP vs ACC⁰), Algorithms from lower bounds techniques.

  
  

  
  

  Μπορείτε να διαβάσετε:

  • Sections 14.1-14.4 from [2]

  
  

  Δείτε επίσης:
  

  
  The Switching Lemma (Ryan O' Donnell)

  
  

  
  

  Thinking Algorithmically About Impossibility (Ryan Williams)

  
  

  Algorithms for Circuits and Circuits for Algorithms: Connecting the Tractable and Intractable (Ryan Williams)
  
• 18 December - 24 December
  

  18 December - 24 December

  Δευτέρα

  • Interactive Proofs: Deterministic verifiers, probabilistic verifiers and the class IP, public and private coins, Arthur-Merlin Games, the class AM and its properties.
    

  
  

  Πέμπτη

  • Interactive Proofs: Shamir's Theorem (IP=PSPACE), Probabilistically Checkable Proofs, The Class PCP[r(n),q(n)].
    

  
  

  
  

  Μπορείτε να διαβάσετε:

  • Sections 8.1-8.4 from [2]

  
  
• 8 January - 14 January
  

  8 January - 14 January

  Δευτέρα

  • Αντί μαθήματος, παρακολούθηση σειράς ομιλιών.
    

  
  

  Πέμπτη

  • Derandomization of Complexity Classes: The Nisan-Wigderson Construction, Worst-case and average case hardness.
  • Παρουσιάσεις φοιτητών.
    
• 15 January - 21 January
  

  15 January - 21 January

  Δευτέρα

  • Derandomization of Complexity Classes: Uniform Derandomization, consequences to Circuit Lower Bounds.
  • Παρουσιάσεις φοιτητών.
  
  

  
  

  Πέμπτη

  • Derandomization of Complexity Classes: The Easy Witness Lemma
  • Παρουσιάσεις φοιτητών.
    

  
  
• 22 January - 28 January
  

  22 January - 28 January

  Δευτέρα

  • Παρουσιάσεις φοιτητών.
  
  

  
  

  Πέμπτη (αναβλήθηκε για 2/2/23, λόγω καιρικών συνθηκών)
  

  • Παρουσιάσεις φοιτητών.