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

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

Μοντέλα τυχαίου υπολογισμού (Las Vegas και Monte Carlo). Δομές δεδομένων. Συναρτήσεις κατάτμησης. Δειγματοληψία. Η εντροπική μέθοδος. Τυχαιοποιημένοι αλγόριθμοι σε γραφήματα. Τυχαιοποιημένοι γεωμετρικοί αλγόριθμοι. Τυχαιοποιημένοι αλγόριθμοι για κατά προσέγγιση μέτρηση. Τυχαιοποιημένοι παράλληλοι αλγόριθμοι. Τεχνικές αποτυχαιοπoίησης. Εργαλεία για την πιθανοτική ανάλυση αλγορίθμων.