Section outline

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

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