Weekly outline

  • General

    Διδάσκοντες

    Ώρες και Μέρος

    Κάθε Τρίτη 17:00 με 20:00, αίθουσα 1.1.29 Παλιά Κτίρια Ηλεκτρολόγων.

    Έναρξη 1 Οκτώβρη.

    (Aναμενόμενα) Θέματα Διαλέξεων

    Αλγόριθμοι ροής δεδομένων (Δομές δεδομένων υπογραμμικού χώρου)

    1. Περίληψη μαθήματος, βασικά πιθανοτικά φράγματα (Markov, Chebyshev), αλγόριθμος του Μόρις. Ιδεαλιστικός αλγόριθμος ροής για μέτρηση πλήθους διαφορετικών στοιχείων. Ανά k ανεξάρτητες συναρτήσεις κατακερματισμού.
    2. Διακριτά στοιχεία, συνέχεια. Υπολογισμοί και αναγκαιότητα της χρήσης πιθανοτικών  αλγορίθμων. Φράγματα Chernoff. AMS σκιαγράφημα.
    3.  Πολυπλοκότητα Επικοινωνίας, απόδειξη αναγκαιότητας της χρήσης πιθανοτικών και προσεγγιστικών αλγορίθμων για το πρόβλημα των διακριτών στοιχείων. Υπολογισμός συχνότητας στοιχείου: CountMin σκιαγράφημα.
    4. Ντετερμινιστικοί αλγόριθμοι για βαρέα στοιχεία, κώδικες Reed-Solomon. Βαρέα στοιχεία στην ell_2 νόρμα: CountSketch σκιαγράφημα.
    5. Βαρέα στοιχεία με γρήγορο χρόνο ανανέωσης και ο κώδικας του Spielman, υπολογισμός διαμέτρου συνόλου σημείων στο επίπεδο.

    Ελάττωση Διάστασης

    1. Λήμμα Johnson-Lindenstrauss, ανισότητα του Khintchine, ανισότητα των Hanson-Wright. Γρήγορος μετασχηματισμός Johnson-Lindenstrauss, ανισότητα Bernstein. 
    2. Αραιός μετασχηματισμός Johnson-Lindenstrauss. Απόδειξη βελτιστότητας του Johnson-Lindenstrauss.

    Ανάκτηση αραιών διανυσμάτων

    1. Γρήγορος Μετασχηματισμός Φουριέ. Επάρκεια ανάκτησης k-αραιού σήματος, μέθοδος του Πρόνυ.
    2. Πολλαπλασιασμός αραιών πολυωνύμων.
    3. Αραιός μετασχηματισμός Φουριέ

    Έλεγχος Ιδιότητας/ υπολογισμός με κατοχή μαντείου

    1. Υπολογισμός τομής πολυγώνων. Προσέγγιση του μέσου βαθμού ενός γραφήματος.
    2. Έλεγχος συνεκτικότητας γραφήματος και υπολογισμός ελάχιστου συνδετικού δέντρου σε υπογραμμικό χρόνο

    Βαθμολογία

    3 σειρές ασκήσεων, τελική παρουσίαση, διαγώνισμα.

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

    Προαπαιτούμενα

    Βασικές γνώσεις θεωρίας Πιθανοτήτων, Αλγόριθμοι και Πολυπλοκότητα.

    Σχετικά μαθήματα

    Jelani Nelson(Harvard) : https://www.sketchingbigdata.org/

    David Woodruff (Carnegie Mellon): http://www.cs.cmu.edu/~dwoodruf/teaching/15859-fall17/index.html

    Moses Charikar (Stanford): https://web.stanford.edu/class/cs369g/

    Piort Indy, Ronnitt Rubinfield (MIT): http://stellar.mit.edu/S/course/6/sp13/6.893/

    Piotr Indyk (MIT): http://people.csail.mit.edu/indyk/MASS/index.html

    Chandra Checkuri (UIUC): https://courses.engr.illinois.edu/cs598csc/fa2014/

    Tim Roughgarden, Gregory Valiant (Stanford): https://csci8980bigdataalgo.wordpress.com

  • 26 September - 2 October

    Eισαγωγή, αλγόριθμος Morris, αλγόριθμος εύρεσης πλήθους διακριτών στοιχείων, ανα k ανεξάρτητες κατανομές.

    Είδαμε τα 3 και 5 (εκτός από 5.2) από 

    http://people.seas.harvard.edu/~minilek/cs229r/fall15/lec/lec1.pdf,

    καθώς και 1 ως 6 (εκτός από το 5 και το δεύτερο παράδειγμα στο 6) από 

    http://people.seas.harvard.edu/~minilek/cs229r/fall15/lec/lec2.pdf

    Η εργασία του Morris λέγεται "Counting large numbers of events in small registers" (1977).

    Για την ιστορία του προβλήματος των διακριτών στοιχείων μπορείτε να διαβάσατε και την εισαγωγή από το https://people.eecs.berkeley.edu/~minilek/publications/papers/f0.pdf (το https://arxiv.org/pdf/1804.01642.pdf περιέχει έναν καλύτερο αλγόριθμο, αλλά σημαντικά λιγότερο λεπτομερή εισαγωγή).





    • 3 October - 9 October

      Συνέχεια ανάλυσης διακριτών στοιχείων 
      Φράγματα Chernoff
      Κάτω φράγματα για ντετερμινιστικούς προσεγγιστικούς αλγόριθμους.
      AMS σκιαγράφημα

    • 10 October - 16 October

      Κάτω φράγματα σε πιθανοτικούς αλγόριθμους για πρόβλημα Διακριτών στοιχείων.
      Πρόβλημα βαρέων στοιχείων και CountMin σκιαγράφημα.

      Ενδιαφέροντα βιντεάκια για κώδικες:

    • 17 October - 23 October

      Γραμμική Σκιαγράφηση.

      Αιτιοκρατικοί αλγόριθμοι για το πρόβλημα των βαρέων στοιχείων στην ell_1 νόρμα μέσω κωδίκων Reed-Solomon.

      Πρόβλημα των βαρέων στοιχείων στην ell_2 νόρμα, CountSketch σκιαγράφημα.

    • 24 October - 30 October

      Γρήγοροι αλγόριθμοι για τα ell_2 βαρεά στοιχεία μέσω κωδίκων επιδιόρθωσης λαθών. 

      Αλγόριθμος ροής για υπολογισμό διαμέτρου.

    • 31 October - 6 November

      Λήμμα Johnson-Lindenstrauss
      Ανισότητα Khintchine
      Ανισότητα Hanson-Wright
      Γρήγορος Μετασχηματισμός Johson-Lindenstrauss
      Aνισότητα Bernstein

      Επιπρόσθετα:
      Eίδαμε ότι μπορώ να βρω εκθετικά πολλά "σχεδόν κάθετα" μοναδιαία διανύσματα ( |<v_i,v_j>| <= ε) στον R^m, και ότι αυτό είναι το δυϊκό πρόβλημα των ε-(μη συνοχικών πινάκων) που είδαμε στο τρίτο μάθημα. Oρίστε διάφορες κατασκευές  και λίγα ιστορικά γεγονότα.


      1. Με τυχαία πρόσημα: Παίρνω n =  2^{( O( ε^2  m )} διανύσματα, με κάθε συντεταγμένη να είναι στην τύχη +- 1 (μπορείς να διαιρέσεις με ριζα( m ) για να γίνουν μοναδιαία). Είτε η ανισότητα του  Khintchine είτε τα φράγματα Chernoff θα δώσουν το ζητούμενο!
      2. Παίρνοντας τυχαία σημεία πάνω στη σφαίρα. Παίρνουμε n =  2^{( O( ε^2   m )} διανύσματα v_1, v_2 .... Κάθε συντεταγμένη του v_j είναι γκαουσιανή, και το κανονικοποιούμε ώστε  να γίνει μοναδιαίο. Η απόδειξη είναι παρόμοια με το Λήμμα Johnson-Lindenstrauss που είδαμε ((υπάρχει μια τεχνικά πιο απλή απόδειξη: παίρνεις κάθε συντεταγμένη γκαουσιάνη και ΔΕΝ κανονικοποιείς, αποδεικνύοντας την "σχεδόν καθετότητα" (αλλά με ε/10 αντί για ε, θα δείτε μετά γιατί) χωρίς να είναι μοναδιαία τα διανύσματα- ωστόσο, η συντριπτική πλειοψηφία θα έχουν μέτρο στο [1/10,  10], οπότε κρατάς μόνο αυτά και πετάς τα υπόλοιπα, κανονικοποιείς και τελείωσες! )).
      3. Με κώδικες επιδιόρθωσης σφαλμάτων:
          i. Όπως είδαμε στο δεύτερο μάθημα, αλλά αλλάζοντας λίγο τις παραμέτρους. Για την ακρίβεια, η κατασκευή στο δεύτερο μάθημα είναι κατασκευή με ε= 1/5 (γιατί; ).
          ii. Με κώδικες Reed-Solomon (πολυώνυμα χαμηλού βαθμού), όπως είδαμε στο πρόβλημα των ell_1 ε-βαρέων στοιχείων.
      4.Μέσω ισοτιμιών με πρώτους αριθμούς. Λέγεται και Κώδικας κινέζικων υπολοίπων. Είναι πάντα χειρότερος είτε από τις τυχαίες κατασκευές είτε από την κατασκευή με τον κώδικα Reed-Solomon. Στα θετικά είναι ότι μπορείς γρήγορα να βρεις το v_j αν σου ζητηθεί (όπως και στους Reed-Solomon κώδικες).
      5. Παίρνοντας στην τύχη έναν m x n υποπίνακα του n x n  πίνακα Walsh-Hadamard (ή οποιουδήποτε άλλου ορθοκανονικού πίνακα με εγγραφές <= 1/ρίζα (n) ), και παίρνοντας ως v_j τη j-οστή στήλη, αφού κανονικοποιήσουμε . Κλασικά, έχουμε n =   2^{( O( ε^2  *m )}. Η απόδειξη είναι μέσω της ανισότητας του Bernstein που είδαμε στο μάθημα.
      6. Μέσω πυρηνικών όπλων (δίνει το ίδιο αποτέλεσμα με Reed-Solomon): Με ένα σπουδαίο αποτέλεσμα του Deligne, ο οποίος απέδειξε μια εικασία του Weil (λέγεται/λεγόταν και υπόθεση του Ρίμαν για ελλειπτικές καμπύλες). Δείτε και εδώ την κατασκευή. Αυτή η ιδέα έχει εφαμοστεί ανεξάρτητα και στους κώδικες BCH.

    • 7 November - 13 November

      Γρήγορος Μετασχηματισμός Φουριέ (FFT)

      Ανάκτηση κ-αραιού διανύσματος από 2κ μετρήσεις.

      • 14 November - 20 November

        Αραιός Μετασχηματισμός Johnson-Lindenstrauss.

        Κάτω φράγμα Johnson-Lindenstrauss, για γραμμικούς μετασχηματισμούς.




        • 21 November - 27 November

        • 28 November - 4 December

          • 5 December - 11 December

          • 12 December - 18 December

          • 19 December - 25 December

            Δεν έγινε μάθημα.

            • 26 December - 1 January

              Δεν έγινε μάθημα.

              • 2 January - 8 January

                Δεν έγινε μάθημα.

                • 9 January - 15 January