Weekly outline

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

  Χειμερινό Εξάμηνο 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: ιστοσελίδα εδώ

  
  

  • Ανακοινώσεις Forum
• 6 October - 12 October
  

  6 October - 12 October

  • Εισαγωγή στην fine-grained complexity File
  • 1η διάλεξη: εικασίες SETH, 3-SUM, Orthogonal Vectors, Shortest Paths File
• 13 October - 19 October
  

  13 October - 19 October

  • 2η διάλεξη: Ορθογώνια διανύσματα, k-SAT και δυσκολία προβλήματων σε συμβολοσειρές. File
• 20 October - 26 October
  

  20 October - 26 October

  • 3η διάλεξη: Διερεύνηση της εικασίας δυσκολίας Συντομότερων Μονοπατιών. Σχέση με (Μιν,+)-γινόμενο, και προβλήματα τριγώνων σε γραφήματα. File
• 27 October - 2 November
  

  27 October - 2 November

  • 4η διάλεξη: Πρόβλημα 3SUM, και εκδοχές του. Δέντρα απόφασης για 3SUM. Συνελτικικό 3SUΜ. File
  • 1st Assignment File
• 3 November - 9 November
  

  3 November - 9 November

  • 5η διάλεξη: Μέθοδος Πολυωνύμων για τα Ορθογώνια Διανύσματα. File
• 10 November - 16 November
  

  10 November - 16 November

  • 6η διαλεξη: (Min,+) συνέλιξη, πρόβλημα σακιδίου και ενδιάμεσα προβλήματα. File
• 17 November - 23 November
  

  17 November - 23 November

  • 7η διάλεξη: Πολλαπλασιασμός πινάκων Boole File
• 24 November - 30 November
  

  24 November - 30 November

  • 8η διάλεξη: εντοπισμός κύκλου σε γράφους File
  • 2nd assignment File
• 1 December - 7 December
  

  1 December - 7 December

  Γρηγορότεροι αλγόριθμοι για το πρόβλημα υπολογισμού του (Min,+) γινομένου για πίνακες που ικανοποιούν το κριτήριο της φραγμένης διαφοράς, και εφαρμογές.
  

  link: https://arxiv.org/abs/1707.05095