Structural Complexity

Type
Elective
Course Description

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

Name Sort descending Year Semester Taught by
Structural Complexity 2023-2024 Fall Aristeidis Pagourtzis, Stathis Zachos
Structural Complexity 2021-2022 Fall Aristeidis Pagourtzis, Stathis Zachos
Structural Complexity 2022-2023 Fall Aristeidis Pagourtzis, Stathis Zachos