Concepedia

Randomized Space Complexity

Randomized Space Complexity is a complexity measure in computational theory that characterizes the minimum amount of memory space required by a probabilistic Turing machine to solve a decision problem with bounded error probability.

41

Publications

5K

Citations

76

Authors

52

Institutions

Publications per year

2017–2026

2

Parents

Publications

41

The Space Complexity of Approximating the Frequency Moments

Noga Alon, Yossi Matias, Márió Szegedy · Journal of Computer and System Sciences · 1999 · 1.2K citations

, , +15

The space complexity of approximating the frequency moments

Noga Alon, Yossi Matias, Márió Szegedy · 1996 · 847 citations

, , +15

Randomness is Linear in Space

Noam Nisan, David Zuckerman · Journal of Computer and System Sciences · 1996 · 652 citations

, , +9

Spectral bloom filters

Saar Cohen, Yossi Matias · 2003 · 395 citations

, , +16

Sieve algorithms for the shortest vector problem are practical

Phong Q. Nguyễn, Thomas Vidick · Journal of Mathematical Cryptology · 2008 · 231 citations · Full text

, , +17

1–5 of 41

Authors

76

  1. YM
    Yossi Matias

    Google (United States), United States

    4 publications · 2.6K citations

    4

    h-index

  2. DP
    David P. Woodruff

    IBM Research - Almaden, United States

    3 publications · 78 citations

    3

    h-index

  3. SC
    Saar Cohen

    Johns Hopkins University Applied Physics Laboratory, United States

    2 publications · 532 citations

    2

    h-index

  4. MP
    Mert Pilancı

    University of California, Berkeley, United States

    2 publications · 166 citations

    2

    h-index

  5. VK
    Valerie King

    University of Victoria, Canada

    2 publications · 107 citations

    2

    h-index

1–5 of 76

Institutions

52

  1. Tel Aviv University

    Tel Aviv, Israel

    3 h-index

    5 publications

    1.9K citations

  2. Stanford University

    Stanford, United States

    2 h-index

    3 publications

    100 citations

  3. The University of Texas at Austin

    Austin, United States

    2 h-index

    2 publications

    715 citations

  4. Hebrew University of Jerusalem

    Jerusalem, Israel

    2 h-index

    2 publications

    721 citations

  5. Lund University

    Lund, Sweden

    2 h-index

    2 publications

    57 citations

  6. Carnegie Mellon University

    Pittsburgh, United States

    2 h-index

    3 publications

    66 citations

  7. Yale University

    New Haven, United States

    2 h-index

    4 publications

    286 citations

  8. RTI International

    Durham, United States

    1 h-index

    1 publications

    32 citations

1–8 of 52

Venues

  1. Journal of Computer and System Sciences

    4 publications · 1.9K citations

    4

    h-index

  2. SIAM Journal on Computing

    3 publications · 238 citations

    3

    h-index

  3. Theoretical Computer Science

    2 publications · 35 citations

    2

    h-index

  4. arXiv (Cornell University)

    Repository · 2 publications · 47 citations

    2

    h-index

  5. Information Processing Letters

    2 publications · 110 citations

    2

    h-index

1–5