Χειμερινό Εξάμηνο 2021-2022
Section outline
-
Προσφέρεται ως "Υπολογιστική Πολυπλοκότητα" στην ΣΗΜΜΥ.
Διδάσκοντες:
- Στάθης Ζάχος, Καθηγητής (zachos@cs.ntua.gr)
- Άρης Παγουρτζής, Αναπλ. Καθηγητής (pagour@cs.ntua.gr)
Βοηθοί Διδασκαλίας:
- Αντώνης Αντωνόπουλος, Υ/Δ (aanton@corelab.ntua.gr)
- Αγγελική Χαλκή, Υ/Δ (achalki@corelab.ntua.gr)
Διαλέξεις:
- Δευτέρα 17:00-20:00 (Παλιά Κτίρια Ηλεκτρολόγων ΕΜΠ, Αίθουσα 1.1.31) & διαδικτυακά (Webex link)
- Πέμπτη 15:00-17:00 (Παλιά Κτίρια Ηλεκτρολόγων ΕΜΠ, Αίθουσα 1.1.31) & διαδικτυακά (Webex link)
Έναρξη μαθημάτων: 11/10/21Περιεχόμενο Μαθήματος:
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.