Concepedia

Nc Complexity Class

The NC Complexity Class is a complexity class consisting of decision problems solvable on a parallel computer in polylogarithmic time using a polynomial number of processors, distinguishing it from other complexity classes by its efficient parallelizability within these resource bounds.

55

Publications

3.2K

Citations

92

Authors

67

Institutions

Publications per year

2017–2026

1

Parents

Publications

55

Bounded-width polynomial-size branching programs recognize exactly those languages in NC1

David A. Mix Barrington · Journal of Computer and System Sciences · 1989 · 407 citations

, , +9

Attribute-based encryption for circuits

S. Gorbunov, Vinod Vaikuntanathan, Hoeteck Wee · 2013 · 399 citations

, , +10

Parallel Quantum Computation and Quantum Codes

Cristopher Moore, Martin Nilsson · SIAM Journal on Computing · 2001 · 176 citations

, , +15

Finite monoids and the fine structure of <i>NC</i> <sup>1</sup>

David A. Mix Barrington, Denis Thérien · Journal of the ACM · 1988 · 164 citations · Full text

, , +13

The complexity of XPath query evaluation

Georg Gottlob, Christoph Koch, Reinhard Pichler · 2003 · 137 citations · Full text

, , +16

1–5 of 55

Authors

92

  1. DA
    David A. Mix Barrington

    University of Massachusetts Amherst, United States

    5 publications · 630 citations

    5

    h-index

  2. DT
    Denis Thérien

    McGill University, Canada

    4 publications · 282 citations

    4

    h-index

  3. PM
    Pierre McKenzie

    Université de Montréal, Canada

    3 publications · 132 citations

    3

    h-index

  4. AW
    Avi Wigderson

    Hebrew University of Jerusalem, Israel

    2 publications · 111 citations

    2

    h-index

  5. JW
    Joe Warren

    Rice University, United States

    2 publications · 42 citations

    2

    h-index

1–5 of 92

Institutions

67

  1. Hebrew University of Jerusalem

    Jerusalem, Israel

    4 h-index

    4 publications

    225 citations

  2. University of Toronto

    Toronto, Canada

    4 h-index

    7 publications

    906 citations

  3. University of Massachusetts Amherst

    Amherst Center, United States

    4 h-index

    5 publications

    664 citations

  4. Stanford University

    Stanford, United States

    3 h-index

    5 publications

    372 citations

  5. University of Illinois Urbana-Champaign

    Urbana, United States

    3 h-index

    3 publications

    108 citations

  6. McGill University

    Montreal, Canada

    3 h-index

    3 publications

    249 citations

  7. Boston College

    Boston, United States

    2 h-index

    2 publications

    58 citations

  8. Purdue University West Lafayette

    West Lafayette, United States

    2 h-index

    4 publications

    102 citations

1–8 of 67

Venues

  1. SIAM Journal on Computing

    7 publications · 363 citations

    7

    h-index

  2. Journal of the ACM

    JACM · 5 publications · 390 citations

    5

    h-index

  3. Algorithmica

    2 publications · 175 citations

    2

    h-index

  4. Journal of Computer and System Sciences

    2 publications · 439 citations

    2

    h-index

  5. ACM Transactions on Computation Theory

    TOCT · 1 publications · 11 citations

    1

    h-index

1–5