Γενικά

Λεπτομερής Πολυπλοκότητα

Χειμερινό εξάμηνο 2020-21

Μέρες-ώρες: Τρίτη 16:00-19:00

Διδάσκοντες: Βασίλης Νάκος, Άρης Παγουρτζής

Webex link: εδώ  (για στοιχεία σύνδεσης δείτε στις Ανακοινώσεις)

Έναρξη: 13/10

Περιεχόμενο: (Ισχυρή) Υπόθεση Εκθετικού Χρόνου και Ορθογώνια Διανύσματα.
Πολυωνυμική Μέθοδος.  Αραιοποίηση. Δυσκολία Μέγιστου Ανεξάρτητου συνόλου
και Μέγιστης Κοινής Υπακολουθίας. (Min,+)-συνέλιξη και δυσκολία
υποτετραγωνικών FPTAS για Άθροισμα Υποσυνόλου και Πρόβλημα Σακιδίου.
Πρόβλημα συντομότερων μονοπατιών. Πολλαπλασιασμός πινάκων Boole.
Δυσκολία προβλημάτων υπολογιστικής γεωμετρίας ως προς το 3SUM.
Λογαριθμική βελτίωση για το 3SUM και δέντρα αποφάσεων. Λεπτομερής
πολυπλοκότητα παραμετρικής και προσεγγιστικής επίλυσης.

Βιβλιογραφία:

To μάθημα δεν έχει σύγγραμα. Θα βασιστεί σε αντίστοιχα μαθήματα που έχουν γίνει στο εξωτερικό.

1. Fine-grained Algorithms and Complexity (MIT):, από Virginia Vasilevska Williams : ιστοσελίδα εδώ

2. Fine-grained complexity theory  (MPI), από Karl Bringmann και Marvin Künnemann: ιστοσελίδα εδώ

3.Complexity-Theory of Polynomial Time Problems (MPI), από Karl Bringmann και Sebastian Krinninger: ιστοσελίδα εδώ