Μητροειδή και παραμετρική πολυπλοκότητα - Φιοραβάντες, Φοίβος-Σωτήριος (Εθνικό Μετσόβιο Πολυτεχνείο. Σχολή Εφαρμοσμένων Μαθηματικών και Φυσικών Επιστημών. Τομέας Μαθηματικών. Εργαστήριο Αλγοριθμικών Εφαρμογών και Λογικής, 2018)
Στην παρούσα εργασία γίνεται μια συνοπτική παρουσίαση ενός σχετικά πρόσφατου και πολλά υποσχόμενου τομέα της υπολογιστικής θεωρίας πολυπλοκότητας, αυτού της Παραμετρικής Πολυπλοκότητας. Παράλληλα παρουσιάζονται τα μητροειδή, μια αφηρημένη αλγεβρική δομή, η οποία αποτελεί κατά κάποιο τρόπο γενίκευση της έννοιας τη γραμμικής ανεξαρτησίας ενός διανυσματικού χώρου. Η δομή των μητροειδών φαίνεται να είναι άρρηκτα συνδεδεμένη με πολλά προβλήματα της επιστήμης των υπολογιστών· ενδεικτικά αναφέρουμε την άμεση σχέση που υπάρχει μεταξύ των μητροειδών και των άπληστων αλγορίθμων. Η μελέτη των μητροειδών, πέραν από το ενδιαφέρον που παρουσιάζει αυτή καθ’ αυτή, έχει γεννήσει μια πληθώρα χρήσιμων εργαλείων. Θα κλείσουμε την εργασία παρουσιάζοντας έναν τυχαιοποιημένο πολυωνυμικό πυρήνα για το πρόβλημα Subset Feedback Vertex Set, στην κατασκευή του οποίου παίζουν καθοριστικό ρόλο κάποια από τα βασικότερα θεωρητικά αποτελέσματα των μητροειδών.