Concepedia

Streaming Lower Bounds

Streaming Lower Bounds is a theoretical framework in computational complexity that establishes fundamental limits on the resources, such as space or time, required by any streaming algorithm to solve a given problem within a specified error tolerance.

73

Publications

3.9K

Citations

132

Authors

72

Institutions

Publications per year

2017–2026

18

Parents

Publications

73

On graph problems in a semi-streaming model

Joan Feigenbaum, Sampath Kannan, Andrew McGregor et al. · Theoretical Computer Science · 2005 · 422 citations

, , +9

Numerical linear algebra in the streaming model

Kenneth L. Clarkson, David P. Woodruff · 2009 · 327 citations

, , +17

Maintaining stream statistics over sliding windows: (extended abstract)

Mayur Datar, Aristides Gionis, Piotr Indyk et al. · 2002 · 256 citations

, , +17

Optimal approximations of the frequency moments of data streams

Piotr Indyk, David P. Woodruff · 2005 · 227 citations

, , +14

Algorithms for distributed functional monitoring

Graham Cormode, S. Muthukrishnan, Ke Yi · ACM Transactions on Algorithms · 2011 · 174 citations

, , +17

1–5 of 73

Authors

132

  1. DP
    David P. Woodruff

    IBM Research - Almaden, United States

    12 publications · 994 citations

    10

    h-index

  2. SA
    Sepehr Assadi

    University of Pennsylvania, United States

    5 publications · 136 citations

    5

    h-index

  3. SK
    Sanjeev Khanna

    University of Pennsylvania, United States

    4 publications · 129 citations

    4

    h-index

  4. PI
    Piotr Indyk

    Massachusetts Institute of Technology, United States

    4 publications · 650 citations

    4

    h-index

  5. VB
    Vladimir Braverman

    Johns Hopkins University, United States

    4 publications · 90 citations

    4

    h-index

1–5 of 132

Institutions

72

  1. IBM (United States)

    Armonk, United States

    7 h-index

    10 publications

    1.2K citations

  2. IBM Research - Almaden

    San Jose, United States

    7 h-index

    10 publications

    1.3K citations

  3. Rutgers, The State University of New Jersey

    New Brunswick, United States

    5 h-index

    7 publications

    435 citations

  4. University of Pennsylvania

    Philadelphia, United States

    5 h-index

    11 publications

    1.6K citations

  5. Yale University

    New Haven, United States

    5 h-index

    9 publications

    1.2K citations

  6. Johns Hopkins University

    Baltimore, United States

    5 h-index

    8 publications

    186 citations

  7. Princeton University

    Princeton, United States

    4 h-index

    10 publications

    255 citations

  8. Massachusetts Institute of Technology

    Cambridge, United States

    4 h-index

    6 publications

    819 citations

1–8 of 72

Venues

  1. DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)

    Repository · 7 publications · 124 citations

    7

    h-index

  2. arXiv (Cornell University)

    Repository · 4 publications · 102 citations

    4

    h-index

  3. ACM Transactions on Algorithms

    TALG · 4 publications · 341 citations

    4

    h-index

  4. Algorithmica

    4 publications · 158 citations

    4

    h-index

  5. Theoretical Computer Science

    2 publications · 452 citations

    2

    h-index

1–5