Concepedia

Deterministic Space Complexity

Deterministic Space Complexity is the measure of the minimum amount of memory space required by a deterministic Turing machine to solve a computational problem as a function of the input size.

23

Publications

912

Citations

54

Authors

44

Institutions

Publications per year

2017–2026

1

Parents

Publications

23

Resilient dictionaries

Irene Finocchi, Fabrizio Grandoni, Giuseppe F. Italiano · ACM Transactions on Algorithms · 2009 · 111 citations

, , +11

Faster deterministic sorting and searching in linear space

Arne Andersson · 2002 · 108 citations

, , +14

Universal games of incomplete information

John H. Reif · 1979 · 77 citations · Full text

, , +13

Straggler Identification in Round-Trip Data Streams via Newton's Identities and Invertible Bloom Filters

David Eppstein, Michael T. Goodrich · IEEE Transactions on Knowledge and Data Engineering · 2010 · 66 citations

, , +13

Estimating the sortedness of a data stream

Parikshit Gopalan, T. S. Jayram, Robert Krauthgamer et al. · 2007 · 63 citations

, , +17

1–5 of 23

Authors

54

  1. MT
    Mikkel Thorup

    AT&T (United States), United States

    2 publications · 71 citations

    2

    h-index

  2. VG
    Viliam Geffert

    University of Pavol Jozef Šafárik, Slovakia

    2 publications · 63 citations

    2

    h-index

  3. RM
    Ryu Mizoguchi

    Kyushu University, Japan

    1 publications · 23 citations

    1

    h-index

  4. YK
    Yukiko Kenmochi⋆

    Université Gustave Eiffel, France

    1 publications · 18 citations

    1

    h-index

  5. AS
    Akihiro Sugimoto

    National Institute of Informatics, Japan

    1 publications · 18 citations

    1

    h-index

1–5 of 54

Institutions

44

  1. AT&T (United States)

    Bedminster, United States

    2 h-index

    2 publications

    71 citations

  2. The University of Texas at Austin

    Austin, United States

    2 h-index

    3 publications

    109 citations

  3. Tokyo University of Agriculture and Technology

    Tokyo, Japan

    1 h-index

    1 publications

    18 citations

  4. University of Rome Tor Vergata

    Rome, Italy

    1 h-index

    2 publications

    222 citations

  5. Paderborn University

    Paderborn, Germany

    1 h-index

    1 publications

    18 citations

  6. University of Pavol Jozef Šafárik

    Košice, Slovakia

    1 h-index

    1 publications

    47 citations

  7. Courant Institute of Mathematical Sciences

    New York, United States

    1 h-index

    1 publications

    41 citations

  8. Nagoya Institute of Technology

    Nagoya, Japan

    1 h-index

    3 publications

    171 citations

1–8 of 44

Venues

  1. Theoretical Computer Science

    3 publications · 75 citations

    3

    h-index

  2. SIAM Journal on Computing

    2 publications · 61 citations

    2

    h-index

  3. Journal of the ACM

    JACM · 1 publications · 41 citations

    1

    h-index

  4. Information Processing Letters

    1 publications · 16 citations

    1

    h-index

  5. IEEE Transactions on Knowledge and Data Engineering

    TKDE · 1 publications · 66 citations

    1

    h-index

1–5