Concepedia

Parallel Complexity Theory

Parallel Complexity Theory is a branch of computational complexity theory that classifies computational problems according to their inherent difficulty in terms of resource requirements when solved on parallel models of computation.

224

Publications

11.5K

Citations

340

Authors

163

Institutions

Publications per year

2017–2026

13

Parents

Children

Publications

224

On Finding Lowest Common Ancestors: Simplification and Parallelization

Baruch Schieber, Uzi Vishkin · SIAM Journal on Computing · 1988 · 535 citations

, , +11

On uniform circuit complexity

Walter L. Ruzzo · Journal of Computer and System Sciences · 1981 · 434 citations

, , +17

Tight Bounds on the Complexity of Parallel Sorting

Tom Leighton · IEEE Transactions on Computers · 1985 · 372 citations

, , +17

Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes

Stephen Cook, Cynthia Dwork, Rüdiger Reischuk · SIAM Journal on Computing · 1986 · 339 citations

, , +15

An O(n2log n) parallel max-flow algorithm

Yossi Shiloach, Uzi Vishkin · Journal of Algorithms · 1982 · 226 citations

, , +12

1–5 of 224

Authors

340

  1. UV
    Uzi Vishkin

    University of Maryland, College Park, United States

    7 publications · 1.3K citations

    7

    h-index

  2. SC
    Stephen Cook

    University of Toronto, Canada

    6 publications · 535 citations

    6

    h-index

  3. JH
    John H. Reif

    Duke University, United States

    5 publications · 350 citations

    5

    h-index

  4. TH
    Torben Hagerup

    Max Planck Society, Germany

    5 publications · 263 citations

    5

    h-index

  5. GE
    Guy E. Blelloch

    Carnegie Mellon University, United States

    5 publications · 456 citations

    5

    h-index

1–5 of 340

Institutions

163

  1. Stanford University

    Stanford, United States

    11 h-index

    23 publications

    1.4K citations

  2. University of Washington

    Seattle, United States

    9 h-index

    12 publications

    698 citations

  3. Carnegie Mellon University

    Pittsburgh, United States

    9 h-index

    17 publications

    644 citations

  4. Max Planck Society

    Munich, Germany

    8 h-index

    11 publications

    482 citations

  5. University of Toronto

    Toronto, Canada

    8 h-index

    10 publications

    447 citations

  6. New York University

    New York, United States

    7 h-index

    9 publications

    757 citations

  7. IBM Research - Thomas J. Watson Research Center

    Yorktown Heights, United States

    7 h-index

    7 publications

    206 citations

  8. Tel Aviv University

    Tel Aviv, Israel

    6 h-index

    7 publications

    1.4K citations

1–8 of 163

Venues

  1. SIAM Journal on Computing

    41 publications · 3.3K citations

    27

    h-index

  2. Journal of the ACM

    JACM · 9 publications · 286 citations

    9

    h-index

  3. Journal of Computer and System Sciences

    7 publications · 916 citations

    7

    h-index

  4. IEEE Transactions on Parallel and Distributed Systems

    TPDS · 7 publications · 181 citations

    7

    h-index

  5. arXiv (Cornell University)

    Repository · 6 publications · 156 citations

    6

    h-index

1–5