Fine-Grained Complexity
Section outline
-
Λεπτομερής Πολυπλοκότητα
Χειμερινό εξάμηνο 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: ιστοσελίδα εδώ
-
Πρώτο μάθημα: Τρίτη 13/10.
Εισαγωγή στη Θεωρία Λεπτομερούς Πολυπλοκότητας. Βασικές εικασίες δυσκολίας: (ισχυρή) υπόθεση υποεκθετικού χρόνου, υπόθεση 3-SUM, υπόθεση ορθογώνιων διανυσμάτων, υπόθεση Συντομότερων Μονοπατιών.
-
Δεύτερο Μάθημα. Ορθογώνια διανύσματα, k-SAT και δυσκολία προβλήματων σε συμβολοσειρές.
-
Διερεύνηση της εικασίας δυσκολίας Συντομότερων Μονοπατιών. Σχέση με (Μιν,+)-γινόμενο, και προβλήματα τριγώνων σε γραφήματα.
-
Πρόβλημα 3SUM, και εκδοχές του. Δέντρα απόφασης για 3SUM. Συνελτικικό 3SUΜ.
-
Μέθοδος Πολυωνύμων για τα Ορθογώνια Διανύσματα.
Δείτε τις σημειώσεις του Karl Bringmann.
-
Το μάθημα δε θα γίνει, λόγω επετείου της 17ης Νοεμβρίου. Θα τα πούμε την άλλη εβδομάδα.
Αντ' αυτού, δείτε μερικά προτεινόμενα θέματα για τελική παρουσίαση (μπορείτε να δουλέψετε σε ομάδες των δύο):
- Δυσκολία δυναμικών προβλημάτων μέσω 3SUM
-SETH-δυσκολία του προβλήματος Αθροίσματος Υποσυνόλου
-Δυσκολία δυναμικών προβλημάτων σε επίπεδα γραφήματα
-Βελτιωμένος αλγόριθμος για πολλαπλασιασμό Μπουλ πινάκων με συνδυαστικές μεθόδους
Για προχωρημένους:
-
(Min,+) συνέλιξη, πρόβλημα σακιδίου και ενδιάμεσα προβλήματα.
-
Πολλαπλασιασμός πινάκων Mπουλ.
-
Γρηγορότεροι αλγόριθμοι για το πρόβλημα υπολογισμού του (Min,+) γινομένου για πίνακες που ικανοποιούν το κριτήριο της φραγμένης διαφοράς, και εφαρμογές. Δείτε εδώ για το άρθρο.