Δομική Πολυπλοκότητα

Section outline

• Select section Χειμερινό Εξάμηνο 2025-2026

  Collapse Expand

  Χειμερινό Εξάμηνο 2025-2026

  Collapse all Expand all

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

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

  • Στάθης Ζάχος, Καθηγητής (zachos@cs.ntua.gr)
  • Νίκος Λεονάρδος, Επίκ. Καθηγητής (nleon@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/25

  
  

  
  

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

  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.
  

  
  
  

  • Select activity Ανακοινώσεις

    

    Ανακοινώσεις Forum
  • Select activity Βιβλιογραφία - Υλικό - Σύνδεσμοι

    

    Βιβλιογραφία - Υλικό - Σύνδεσμοι Page
  • Select activity Διαθέσιμες Ομιλίες - Available Presentation Topics

    

    Διαθέσιμες Ομιλίες - Available Presentation Topics Page
  • Select activity Lecture Slides

    

    Lecture Slides Folder
  • Select activity Fine-Grained Complexity Slides (latest dev version)

    

    Fine-Grained Complexity Slides (latest dev version) URL
• Select section Εβδομάδα 1

  Collapse Expand

  Εβδομάδα 1

  1) Δευτέρα 6 Οκτωβρίου

  • Basic notions and results of Complexity Theory: Problems, Turing Machines and their properties.

   

  2) Πέμπτη 9 Οκτωβρίου

  • Basic notions and results of Complexity Theory: Complexity Measures, Complexity Classes, Hierarchy Theorems. 

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

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

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

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

  Collapse Expand

  Εβδομάδα 2

  3) Δευτέρα 13 Οκτωβρίου

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

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

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

   

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

  • Landscape of Computational Complexity Poster

   

  4) Πέμπτη 16 Οκτωβρίου

  • Oracles & The Polynomial Hierarchy: The Polynomial Hierarchy, definition and properties.

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

    • Ch. 17 from [1]

   
• Select section Εβδομάδα 3

  Collapse Expand

  Εβδομάδα 3

  5) Δευτέρα 20 Οκτωβρίου

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

  
  

   

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

  • Fine-Grained Complexity: Introduction to fine-grained complexity: Subexponential time, subexponential reductions, the Exponential Time Hypothesis (ETH), the Strong Exponential Time Hypothesis.

   

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

  • Virginia Vassilevska Williams, On some fine-grained questions in algorithms and complexity
  • Karl Bringmann, Marvin Künnemann, Introduction to Fine-Grained Complexity Theory
• Select section Εβδομάδα 4

  Collapse Expand

  Εβδομάδα 4

  7) Δευτέρα 27 Οκτωβρίου

  • Fine-Grained Complexity: ETH and SETH, the Sparsification Lemma and applications. SETH implies ETH via sparsification. Fine-Grained reductions.

   

   

  8) Πέμπτη 30 Οκτωβρίου

  • Fine-Grained Complexity: Fine-Grained reductions. Main barriers, 3SUM, SETH and APSP hardness, and the web of fine-grained reductions. Orthogonal Vectors and variations. SETH hardness of OV, the Hitting Set Conjecture. Hitting Set Conjecture implies Orthogonal Vectors Conjecture.

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

  • Karl Bringmann, Marvin Künnemann, (Strong) Exponential Time Hypothesis
• Select section Εβδομάδα 5

  Collapse Expand

  Εβδομάδα 5

  9) Δευτέρα 3 Νοεμβρίου

  • Non-Uniform Complexity: Boolean circuits, the class P/poly and related results, Turing Machines with advice, Karp-Lipton Theorem.

   

  10) Πέμπτη 6 Νοεμβρίου

  • Non-Uniform Complexity: Algorithms for Circuit Analysis. 

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

  • Sections 6.1-6.7 from [2]
• Select section Εβδομάδα 6

  Collapse Expand

  Εβδομάδα 6

  11) Δευτέρα 10 Νοεμβρίου

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

   

  12) Πέμπτη 13 Νοεμβρίου

  • Non-Uniform Complexity: Lower bounds for AC⁰: Random restrictions, Håstad's Switching Lemma and applications. Lower bounds from algorithms (NEXP vs ACC⁰).

  
  The Switching Lemma (Ryan O' Donnell)

   

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

    • Sections 14.1-14.2 from [2]
• Select section Εβδομάδα 7

  Collapse Expand

  Εβδομάδα 7

  Δευτέρα 17 Νοεμβρίου

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

   

  13) Πέμπτη 20 Νοεμβρίου

  • Non-Uniform Complexity: Circuits with counting gates, The class ACC⁰, The polynomial method in Circuit Complexity, Razborov-Smolensky Theorem. Algorithms from lower bounds techniques. Monotone functions and circuit lower bounds. Natural proofs: the Circuit Complexity Barrier.

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

  • Sections 14.1-14.2, Chapter 23 from [2]

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

   

  Thinking Algorithmically About Impossibility (Ryan Williams)

   

  Algorithms for Circuits and Circuits for Algorithms: Connecting the Tractable and Intractable (Ryan Williams)