Topic outline

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

    Προσφέρεται σε αυτό το εξάμηνο στο διδακτορικό πρόγραμμα της ΣΗΜΜΥ αντί του μαθήματος "Προχωρημένα Θέματα Θεωρητικής Πληροφορικής: Θεωρία Αριθμών και Κρυπτογραφία". 

    Προσφέρεται επίσης στα ΔΠΜΣ ΑΛΜΑ, ΕΜΕ, Μαθηματική Προτυποποίηση.

    Διδάσκοντες:

    Βοηθός Διδασκαλίας:

    Διαλέξεις:
    • Πέμπτη 16:00-20:00 (Παλιά Κτίρια Ηλεκτρολόγων ΕΜΠ, Αίθουσα 1.1.31) & διαδικτυακά (Webex link)

    Έναρξη μαθημάτων: 03/03/22


    Περιεχόμενο Μαθήματος:
    Εισαγωγή στα προβήματα μέτρησης λύσεων και την κλάση #P. Μετρητικά προβλήματα επιλύσιμα σε πολυωνυμικό χρόνο (Μέτρηση τέλειων ταιριασμάτων σε επίπεδους γράφους, Ολογραφικοί αλγόριθμοι). Προβλήματα μέτρησης ομομορφισμών, #CSP, προβλήματα Holant. Θεωρήματα διχοτομίας για προβλήματα μέτρησης. Αποδοτικοί προσεγγιστικοί αλγόριθμοι (FPTAS, FPRAS) για μετρητικά προβλήματα. Στατιστική Φυσική και η συνάρτηση διαμέρισης (partition function). Περιγραφική πολυπλοκότητα για κλάσεις προβλημάτων μέτρησης.

  • Υλικό - Βιβλιογραφία

    Βιβλιογραφία

    1. Jin-Yi Cai and Xi Chen. Complexity Dichotomies for Counting Problems: Volume 1, Boolean Domain, Cambridge University Press, 2017
    2. Mark Jerrum. Counting and Markov chains: CMU Math
    3. Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach, Cambridge University Press, 2009
    4. Neil Immerman. Descriptive Complexity, Springer Graduate Texts in Computer Science, 1999.

    Surveys

    1. Mark Jerrum. Counting Constraint Satisfaction Problems.
    2. Pinyam Lu. Complexity Dichotomies for Counting Problems.
    3. Alan Frieze and Eric Vigoda. A survey on the use of Markov chains to randomly sample colorings.


    Papers

    1. Sanjeev Saluja, K.V. Subrahmanyam and Madhukar N. Thakur. Descriptive Complexity of #P Functions. Journal of Computer and System Sciences 50.3, pages 493–505 (1995).
    2. Marcelo Arenas, Martin Muñoz, and Cristian Riveros. Descriptive Complexity for Counting Complexity Classes. Log. Methods Comput. Sci. 16.1 (2020).
    3. Andrei A. Bulatov, Víctor Dalmau, and Marc Thurley. Descriptive complexity of approximate counting CSPs. In Computer Science Logic 2013 (CSL 2013), volume 23 of LIPIcs , pages 149–164 (2013).
    4. Martin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, and Mark Jerrum. The relative complexity of approximate counting problems. Algorithmica, 38(3), pages 471–500 (2004).
    5. Mark Jerrum, Alistair Sinclair, and Eric Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. Journal of the ACM, 51(4), pages 671–697 (2004).



    • Διαλέξεις

      • Διάλεξη 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, Ηρώ Οικονόμου

      • Ασκήσεις

        • Προτεινόμενα θέματα ομιλιών

          FPRAS for counting problems
          1. FPRAS for #Matchings (Jerrum & Sinclair, The Markov chain Monte Carlo method: an approach to approximate counting and integration (sections 12.1-12.4))

          2. FPRAS for the Permanent (Jerrum, Sinclair & Vigoda, A Polynomial-time Approximation Algorithm for the Permanent of a Matrix with Nonnegative Entries)

          3. FPRAS for #NFA (Arenas, Croquevielle, Jayaram & Riveros, #NFA admits an FPRAS: efficient enumeration, counting, and uniform generation for logspace classes)


          Classification of counting problems with respect to approximability
          4. The relative complexity of approximate counting (Dyer, Goldberg, Greenhill & Jerrum, On the relative complexity of approximate counting)

          5. An approximation trichotomy for boolean #CSP (Dyer, Goldberg & Jerrum, An approximation trichotomy for Boolean #CSP)

          6. Approximating Holant problems (McQuillan, Approximating holant problems by winding)


          Dichotomy theorems
          7. Counting graph homomorphisms (Chen, Curticapean & Dell, The Exponential-Time Complexity of Counting (Quantum) Graph Homomorphisms)

          8. Counting weighted Boolean #CSP (Dyer, Goldberg & Jerrum, The complexity of weighted Boolean #CSP)


          Descriptive complexity
          9. Descriptive complexity of approximate counting CSPs (Bulatov, Dalmau & Thurley, Descriptive complexity of approximate counting CSPs)