Weekly outline

  • Χειμερινό Εξάμηνο 2021-2022

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

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

    Αίθουσα: 1.1.31, Παλ. Κτ. Ηλεκτρολόγων ΕΜΠ & διαδικτυακά 

    Έναρξη: 12/10/2021

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

    Περιεχόμενο: (Ισχυρή) Υπόθεση Εκθετικού Χρόνου και Ορθογώνια Διανύσματα.
    Πολυωνυμική Μέθοδος.  Αραιοποίηση. Δυσκολία Μέγιστου Ανεξάρτητου συνόλου
    και Μέγιστης Κοινής Υπακολουθίας. (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: ιστοσελίδα εδώ