Concepedia

Parallel Algorithmic Lower Bounds

Parallel Algorithmic Lower Bounds is a theoretical framework in computational complexity that establishes minimum resource requirements, such as time or processor bounds, for solving problems on parallel models of computation, distinguishing it from sequential lower bounds by explicitly accounting for parallelism's impact on computational limits.

42

Publications

1.6K

Citations

86

Authors

51

Institutions

Publications per year

2017–2026

7

Parents

Publications

42

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

A complexity theory of efficient parallel algorithms

Clyde P. Kruskal, Larry Rudolph, Marc Snir · Theoretical Computer Science · 1990 · 228 citations

, , +12

On Parallel Searching

Marc Snir · SIAM Journal on Computing · 1985 · 110 citations

, , +17

Time and Parallel Processor Bounds for Linear Recurrence Systems

Shyh-Ching Chen, David J. Kuck · IEEE Transactions on Computers · 1975 · 94 citations

, , +17

Bounds on the time for parallel RAM's to compute simple functions

Stephen Cook, Cynthia Dwork · 1982 · 77 citations · Full text

, , +13

1–5 of 42

Authors

86

  1. MS
    Marc Snir

    University of Illinois Urbana-Champaign, United States

    3 publications · 348 citations

    3

    h-index

  2. CP
    Clyde P. Kruskal

    University of Maryland, College Park, United States

    2 publications · 238 citations

    2

    h-index

  3. AS
    Aaron Sidford

    Stanford University, United States

    2 publications · 22 citations

    2

    h-index

  4. SB
    Sébastien Bubeck

    Microsoft (United States), United States

    2 publications · 22 citations

    2

    h-index

  5. QJ
    Qijia Jiang

    Stanford University, United States

    2 publications · 22 citations

    2

    h-index

1–5 of 86

Institutions

51

  1. University of Illinois Urbana-Champaign

    Urbana, United States

    3 h-index

    5 publications

    304 citations

  2. The Ohio State University

    Columbus, United States

    3 h-index

    5 publications

    81 citations

  3. University of Washington

    Seattle, United States

    3 h-index

    3 publications

    34 citations

  4. Stanford University

    Stanford, United States

    3 h-index

    6 publications

    79 citations

  5. ETH Zurich

    Zurich, Switzerland

    2 h-index

    10 publications

    132 citations

  6. Seattle University

    Seattle, United States

    2 h-index

    2 publications

    22 citations

  7. Zhejiang University

    Hangzhou, China

    1 h-index

    4 publications

    48 citations

  8. National Center for Supercomputing Applications

    Sofia, Bulgaria

    1 h-index

    1 publications

    110 citations

1–8 of 51

Venues

  1. SIAM Journal on Computing

    4 publications · 508 citations

    4

    h-index

  2. Information Processing Letters

    3 publications · 49 citations

    3

    h-index

  3. Theoretical Computer Science

    3 publications · 273 citations

    3

    h-index

  4. IEEE Transactions on Computers

    3 publications · 172 citations

    3

    h-index

  5. arXiv (Cornell University)

    Repository · 3 publications · 40 citations

    3

    h-index

1–5