Concepedia

Space-bounded Computation

Space-Bounded Computation is a computational process in which the amount of memory space used by an algorithm is restricted by a function of the input size, typically expressed as a bound on the number of tape cells used by a Turing machine during its execution.

54

Publications

3.8K

Citations

94

Authors

61

Institutions

Publications per year

2017–2026

2

Parents

Publications

54

Space-efficient online computation of quantile summaries

Michael B. Greenwald, Sanjeev Khanna · 2001 · 456 citations

, , +14

Pseudorandom generators for space-bounded computation

Noam Nisan · COMBINATORICA · 1992 · 427 citations

, , +10

Pseudorandom generators for space-bounded computations

Noam Nisan · 1990 · 229 citations

, , +11

Random sampling techniques for space efficient online computation of order statistics of large datasets

Gurmeet Singh Manku, Sridhar Rajagopalan, Bruce G. Lindsay · ACM SIGMOD Record · 1999 · 198 citations · Full text

, , +11

A Combinatorial Problem Which Is Complete in Polynomial Space

Shimon Even, Robert E. Tarjan · Journal of the ACM · 1976 · 169 citations · Full text

, , +12

1–5 of 54

Authors

94

  1. JŠ
    Janoš Šimon

    Pennsylvania State University, United States

    3 publications · 162 citations

    3

    h-index

  2. PC
    Pierluigi Crescenzi

    University of Florence, Italy

    2 publications · 28 citations

    2

    h-index

  3. WL
    Walter L. Ruzzo

    University of Washington, United States

    2 publications · 141 citations

    2

    h-index

  4. JG
    John Greiner

    Carnegie Mellon University, United States

    2 publications · 175 citations

    2

    h-index

  5. BG
    Bruce G. Lindsay

    Pennsylvania State University, United States

    2 publications · 288 citations

    2

    h-index

1–5 of 94

Institutions

61

  1. IBM Research - Almaden

    San Jose, United States

    5 h-index

    9 publications

    1K citations

  2. Princeton University

    Princeton, United States

    3 h-index

    6 publications

    126 citations

  3. University of Waterloo

    Waterloo, Canada

    3 h-index

    3 publications

    111 citations

  4. Massachusetts Institute of Technology

    Cambridge, United States

    3 h-index

    4 publications

    289 citations

  5. IBM (United States)

    Armonk, United States

    3 h-index

    6 publications

    885 citations

  6. University of Washington

    Seattle, United States

    3 h-index

    5 publications

    321 citations

  7. Pennsylvania State University

    State College, United States

    3 h-index

    4 publications

    183 citations

  8. University of Edinburgh

    Edinburgh, United Kingdom

    2 h-index

    3 publications

    228 citations

1–8 of 61

Venues

  1. Theoretical Computer Science

    4 publications · 103 citations

    4

    h-index

  2. SIAM Journal on Computing

    4 publications · 87 citations

    4

    h-index

  3. Journal of Computer and System Sciences

    3 publications · 196 citations

    3

    h-index

  4. ArXiv.org

    Repository · 2 publications · 26 citations

    2

    h-index

  5. Information and Control

    2 publications · 188 citations

    2

    h-index

1–5