Work-depth Tradeoffs

Work-Depth Tradeoffs is a theoretical framework in parallel computation that characterizes the inherent balance between the total computational effort (work) and the critical path length (depth) in parallel algorithms, distinguishing it from models that optimize one metric independently of the other.

Publications

237

Citations

Authors

Institutions

Publications per year

2017–2026

Parents

Parallel Computation

Publications

A provable time and space efficient implementation of NESL

Guy E. Blelloch, John Greiner · 1996 · 141 citations

Computing, Computer Engineering, Computer Science +17

A provable time and space efficient implementation of NESL

Guy E. Blelloch, John Greiner · ACM SIGPLAN Notices · 1996 · 34 citations

Computing, Computer Engineering, Computer Science +17

Parallel Reachability in Almost Linear Work and Square Root Depth

Yang P. Liu, Arun Jambulapati, Aaron Sidford · 2019 · 22 citations

Computing, Computer Science, Algorithms +16

Parallel Minimum Cuts in Near-linear Work and Low Depth

Barbara Geissmann, Lukas Gianinazzi · 2018 · 16 citations · Full text

Computing, Computer Science, Algorithms +15

Automatic complexity analysis of explicitly parallel programs

Torsten Hoefler, Grzegorz Kwaśniewski · 2014 · 13 citations

Computing, Computer Engineering, Computer Science +16

1–5 of 6

Authors

YP
Yang P. Liu
Stanford University, United States
2 publications · 33 citations
2
h-index
AJ
Arun Jambulapati
Stanford University, United States
2 publications · 33 citations
2
h-index
AS
Aaron Sidford
Stanford University, United States
2 publications · 33 citations
2
h-index
GE
Guy E. Blelloch
Carnegie Mellon University, United States
2 publications · 175 citations
2
h-index
JG
John Greiner
Carnegie Mellon University, United States
2 publications · 175 citations
2
h-index

1–5 of 9

Institutions

1–4 of 4

Venues

arXiv (Cornell University)
Repository · 1 publications · 11 citations
1
h-index
ACM SIGPLAN Notices
1 publications · 34 citations
1
h-index

1–2