Concepedia

Sublinear-time Linear Algebra

Sublinear-Time Linear Algebra is a computational framework within the field of sublinear algorithms that enables the approximation of fundamental linear algebra operations—such as matrix multiplication, norm estimation, and low-rank approximation—in time sublinear in the size of the input matrices, thereby distinguishing itself from classical linear algebra algorithms by prioritizing computational efficiency over exact computation.

8

Publications

672

Citations

9

Authors

8

Institutions

Publications per year

2017–2026

4

Parents

Publications

8

Sublinear time algorithms for metric space problems

Piotr Indyk · 1999 · 202 citations

, , +11

Solving linear programs in the current matrix multiplication time

Michael B. Cohen, Yin Tat Lee, Zhao Song · 2019 · 154 citations

, , +14

Solving Linear Programs in the Current Matrix Multiplication Time

Michael B. Cohen, Yin Tat Lee, Zhao Song · Journal of the ACM · 2021 · 132 citations · Full text

, , +14

The bilinear complexity and practical algorithms for matrix multiplication

Computational Mathematics and Mathematical Physics · 2013 · 105 citations

, , +16

Lower bounds for the multiplicative complexity of matrix multiplication

Markus Bläser · Computational Complexity · 1999 · 26 citations

, , +16

1–5 of 8

Authors

9

  1. YT
    Yin Tat Lee

    University of Washington, United States

    3 publications · 307 citations

    3

    h-index

  2. ZS
    Zhao Song

    The University of Texas at Austin, United States

    3 publications · 307 citations

    3

    h-index

  3. MB
    Michael B. Cohen

    Massachusetts Institute of Technology, United States

    3 publications · 307 citations

    3

    h-index

  4. MB
    Markus Bläser

    University of Lübeck, Germany

    1 publications · 26 citations

    1

    h-index

  5. PI
    Piotr Indyk

    Massachusetts Institute of Technology, United States

    1 publications · 202 citations

    1

    h-index

1–5 of 9

Institutions

8

  1. The University of Texas at Austin

    Austin, United States

    3 h-index

    3 publications

    307 citations

  2. Massachusetts Institute of Technology

    Cambridge, United States

    3 h-index

    3 publications

    307 citations

  3. University of Washington

    Seattle, United States

    3 h-index

    4 publications

    461 citations

  4. Google (United States)

    Mountain View, United States

    1 h-index

    2 publications

    44 citations

  5. University of Bonn

    Bonn, Germany

    1 h-index

    1 publications

    26 citations

  6. Carnegie Mellon University

    Pittsburgh, United States

    1 h-index

    2 publications

    20 citations

  7. Stanford University

    Stanford, United States

    1 h-index

    1 publications

    202 citations

  8. Microsoft (United States)

    Redmond, United States

    1 h-index

    1 publications

    154 citations

1–8 of 8

Venues

  1. arXiv (Cornell University)

    Repository · 3 publications · 53 citations

    3

    h-index

  2. Journal of the ACM

    JACM · 1 publications · 132 citations

    1

    h-index

  3. Computational Complexity

    CC · 1 publications · 26 citations

    1

    h-index

  4. 1

    h-index

1–4