Section outline

  • 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)