Concepedia

Counting Complexity

Counting Complexity is a branch of computational complexity theory that classifies computational problems based on the difficulty of counting the number of solutions to decision problems in NP, rather than determining the existence of such solutions.

121

Publications

5.4K

Citations

187

Authors

120

Institutions

Publications per year

2017–2026

12

Parents

Publications

121

The Complexity of Counting in Sparse, Regular, and Planar Graphs

Salil Vadhan · SIAM Journal on Computing · 2001 · 260 citations · Full text

, , +16

The Parameterized Complexity of Counting Problems

Jörg Flum, Martin Grohe · SIAM Journal on Computing · 2004 · 242 citations

, , +15

The complexity of approximate counting

Larry Stockmeyer · 1983 · 209 citations · Full text

, , +17

The Relative Complexity of Approximate Counting Problems

Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill et al. · Algorithmica · 2003 · 208 citations

, , +14

Complexity of the Two-Variable Fragment with Counting Quantifiers

Ian Pratt‐Hartmann · Journal of Logic Language and Information · 2005 · 188 citations

, , +11

1–5 of 121

Authors

187

  1. JC
    Jin‐Yi Cai

    University of Wisconsin–Madison, United States

    11 publications · 450 citations

    10

    h-index

  2. AD
    Arnaud Durand

    Université Paris Cité, France

    6 publications · 165 citations

    6

    h-index

  3. LA
    Leslie Ann Goldberg

    University of Warwick, United Kingdom

    6 publications · 362 citations

    6

    h-index

  4. PL
    Pinyan Lu

    Microsoft Research Asia (China), China

    5 publications · 255 citations

    5

    h-index

  5. MH
    Miki Hermann

    Centre National de la Recherche Scientifique, France

    5 publications · 135 citations

    5

    h-index

1–5 of 187

Institutions

120

  1. University of Wisconsin–Madison

    Madison, United States

    10 h-index

    16 publications

    497 citations

  2. Université Paris Cité

    Paris, France

    9 h-index

    9 publications

    283 citations

  3. Centre National de la Recherche Scientifique

    Paris, France

    8 h-index

    13 publications

    205 citations

  4. Queen Mary University of London

    London, United Kingdom

    6 h-index

    6 publications

    98 citations

  5. University of Leeds

    Leeds, United Kingdom

    6 h-index

    7 publications

    460 citations

  6. Massachusetts Institute of Technology

    Cambridge, United States

    6 h-index

    8 publications

    341 citations

  7. University of Oxford

    Oxford, United Kingdom

    6 h-index

    10 publications

    295 citations

  8. Lund University

    Lund, Sweden

    5 h-index

    10 publications

    362 citations

1–8 of 120

Venues

  1. Theoretical Computer Science

    7 publications · 329 citations

    7

    h-index

  2. Journal of Computer and System Sciences

    6 publications · 134 citations

    6

    h-index

  3. SIAM Journal on Computing

    6 publications · 850 citations

    6

    h-index

  4. Journal of the ACM

    JACM · 4 publications · 286 citations

    4

    h-index

  5. arXiv (Cornell University)

    Repository · 4 publications · 44 citations

    4

    h-index

1–5