Αλγόριθμοι τοπικού υπολογισμού και εφαρμογές τους - Ματίκας, Γεώργιος (Εθνικό Μετσόβιο Πολυτεχνείο. Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών. Τομέας Τεχνολογίας Πληροφορικής και Υπολογιστών. Εργαστήριο Λογικής και Επιστήμης Υπολογισμών, 2016)
Τα τελευταία χρόνια παρατηρείται το φαινόμενο τα σύνολα δεδομένων που δίνονται ως είσοδοι σε αλγόριθμους προς επεξεργασία να είναι ασύλληπτα μεγάλα. Λογικό είναι, λοιπόν, ο χρόνος που θα κάνει ο αλγόριθμος να τα επεξεργαστεί να είναι εξίσου πολύς. Πολλές φορές, όμως, χρειαζόμαστε τα αποτελέσματα σε σύντομο χρονικό διάστημα ώστε να πάρουμε άμεσα κάποια απόφαση. Γι' αυτό και το ενδιαφέρον έχει στραφεί πλέον προς τους αλγόριθμους που τρέχουν σε υπογραμμικό χρόνο σε σχέση με το μέγεθος της εισόδου. Στην περίπτωση που δεν μας ενδιαφέρει ολόκληρη η λύση του προβλήματος, αλλά αρκούμαστε σε ένα μικρό μέρος αυτής κάθε φορά, μπορούμε να χρησιμοποιήσουμε έναν αλγόριθμο τοπικού υπολογισμού οι οποίοι παρουσιάζονται στην εργασία αυτή. Παρουσιάζονται δύο παράλληλοι αλγόριθμοι που τρέχουν σε υπογραμμικό χρόνο. Στη συνέχεια δίνονται αλγόριθμοι τοπικού υπολογισμού για αρκετά σημαντικά γραφοθεωρητικά προβλήματα που βασίζονται στους προηγούμενους, και συγκεκριμένα για τα προβλήματα του maximal independent set, του 2-χρωματισμού υπεργράφου και του maximal matching. Συζητούνται, επίσης, εφαρμογές αυτού του είδους αλγορίθμων σε διάφορες περιοχές της Επιστήμης Υπολογιστών, όπως ο Σχεδιασμός Μηχανισμών και το Probabilistic Inference.