Section outline

    • Διάλεξη 3/3/2022: Βασικές έννοιες Υπολογιστικής Πολυπλοκότητας. Κλάσεις Πολυπλοκότητας. Τυχαιότητα. Προσεγγιστικοί αλγόριθμοι. Εισαγωγή στη Μετρητική Πολυπλοκότητα. Η κλάση #P. Παραδείγματα προβλημάτων της κλάσης #P. Aναγωγές μεταξύ μετρητικών συναρτήσεων.
    • Διάλεξη 10/3/2022: Πληρότητα ως προς τα δύο είδη αναγωγών. Βασικές σχέσεις κλάσεων συναρτήσεων. Τρεις κλάσεις μετρητικών προβλημάτων: Μέτρηση ομομορφισμών γράφων, Μετρητικά CSPs, Προβλήματα Holant. (βιβλίο 1. σελ. 1-11) (webex recording)
    • Διάλεξη 17/3/2022: Προβλήματα Holant. Πύλες που πραγματοποιούν συναρτήσεις. Ολογραφικοί μετασχηματισμοί. Το θεώρημα Holant του Valiant. Εισαγωγή στον αλγόριθμο FKT. (βιβλίο 1. σελ. 12-24)
    • Διάλεξη 24/3/2022: Ο αλγόριθμος FKT για τη μέτρηση τέλειων ταιριασμάτων σε επίπεδους γράφους. Matchgates. Εισαγωγή στους ολογραφικούς αλγόριθμους. (βιβλίο 2. σελ. 4-9, βιβλίο 1. σελ. 105-107) (webex recording)
    • Διάλεξη 31/3/2022: Ολογραφικός αλγόριθμος για το πρόβλημα #PL-3-NAE-ICE. Πολυωνυμική παρεμβολή ως μέθοδος απόδειξης #P-δυσκολίας. Θεωρήματα διχοτομίας για προβλήματα ομομορφισμών γράφων (απόφασης και μετρητικά). (βιβλίο 1. σελ. 106-116, survey 1.) (webex recording)
    • Διάλεξη 7/4/2022: Θεωρήματα διχοτομίας για προβλήματα μέτρησης ομομορφισμών γράφων και #CSPs. Δειγματοληψία και μέτρηση λύσεων. Ορισμός fpras, uniform sampler και total variation distance. (surveys 1, 2 και βιβλίο 2. σελ. 23-25) (webex recording)
    • Διάλεξη 14/4/2022: Oρισμός fpaus. Η μέθοδος Monte Carlo. fpras για το πρόβλημα #DNF. Σχέση μεταξύ προσεγγιστικής μέτρησης και σχεδόν ομοιόμορφης δειγματοληψίας. Απόδειξη της πρότασης ότι fpaus για το πρόβλημα ταιριασμάτων συνεπάγεται fpras για τη μέτρηση ταιριασμάτων. Εισαγωγή στις Μαρκοβιανές αλυσίδες. Οι ιδιότητες μη αναγωγιμότητας και απεριοδικότητας. (βιβλίο 2. σελ. 25-28) (webex recording)
    • Διάλεξη 5/5/2022: Εργοδικές Μαρκοβιανές αλυσίδες. Ορισμός της στάσιμης κατανομής και του χρόνου σύγκλισης. Μαρκοβιανή αλυσίδα για το πρόβλημα χρωματισμού ενός γράφου με q χρώματα, όταν q>4Δ. Ανάλυση του χρόνου σύγκλισης με τη χρήση σύζευξης (coupling) Μαρκοβιανών αλυσίδων. (βιβλίο 2. σελ. 28-38) (webex recording)
    • Διάλεξη 12/5/2022: Path coupling. Μαρκοβιανή αλυσίδα για το πρόβλημα χρωματισμού ενός γράφου με q χρώματα, όταν q>2Δ. Ανάλυση του χρόνου σύγκλισης με τη χρήση path coupling. Περιγραφική πολυπλοκότητα για προβλήματα απόφασης. Θεώρημα Fagin. Λογικός χαρακτηρισμός της #P. (βιβλίο 2. σελ. 28-38, βιβλίο 4. σελ. 113-117, paper 1.) (webex recording)
    • Διάλεξη 19/5/2022: Παραδείγματα έκφρασης NP και #P προβλημάτων στις λογικές ESO (Existential Second-order) και #FO (#First-order) αντίστοιχα. Ιεραρχία στην #FO. Μετρητικά προβλήματα με αντίστοιχο εύκολο πρόβλημα απόφασης. Οι κλάσεις #PE και TotP. H κλάση #Σ1, μια κλάση που περιέχει προβλήματα με fpras. Η κλάση ΣQSO(FO), ένας εναλλακτικός χαρακτηρισμός της #P. (paper 1, paper 2.) (webex recording)
    • Διάλεξη 26/5/2022: Ομιλία του Αντρέα Γκέμπελ με θέμα: "Sampling and approximation algorithms for Gibbs point processes". (webex recording)
    • Διάλεξη 5/6/2022: Ομιλίες φοιτητών:
    1. On the relative complexity of approximate counting problems, Ιωάννης Ιακωβίδης
    2. Descriptive complexity of approximate counting CSPs, Χρήστος Δουλάμης
    3. FPRAS for the permanent, Ηρώ Οικονόμου