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

Τύπος
Επιλογής
Περιγραφή μαθήματος

Διαδραστικές αποδείξεις. Πιθανοτικά ελέγξιμες συναρτήσεις. Το θεώρημα PCP. Το θεώρημα του Razborov. Πολυπλοκότητα προβλημάτων μέτρησης. Τα θεωρήματα των Valliant και Toda. Προσεγγιστική μέτρηση. Μέτρο και διάσταση σε κλάσεις πολυπλοκότητας. Ψευδοτυχαιότητα. Γραφήματα εξαπλωτές. Μονόδρομες συναρτήσεις. Αποτυχαιοποίηση (ομοιόμορφη και μη). Πολυπλοκότητα και υπολογισμός σε πραγματικούς αριθμούς, πολυπλοκότητα αποδείξεων, επικοινωνιακή πολυπλοκότητα, παραμετρική πολυπλοκότητα, πολυπλοκότητα μέσου όρου.

Ειδικά Θέματα Διακριτών Μαθηματικών

Τύπος
Επιλογής
Περιγραφή μαθήματος

Στο μάθημα αυτό θα διδάσκονται σύγχρονα θέματα διακριτών μαθηματικών που δεν καλύπτονται από τα υπόλοιπα μαθήματα του προγράμματος.