Concepedia

Algorithmic Lower Bounds

Algorithmic Lower Bounds is a theoretical construct in computer science that establishes the minimum computational resources, such as time or space, required by any algorithm to solve a given problem, thereby providing a fundamental limit against which algorithmic efficiency can be measured.

398

Publications

18.1K

Citations

735

Authors

332

Institutions

Publications per year

2017–2026

86

Parents

Publications

398

A metric for distributions with applications to image databases

Yossi Rubner, Carlo Tomasi, Leonidas Guibas · 2002 · 1.7K citations

, , +14

Lower bounds for algebraic computation trees

Michael Ben-Or · 1983 · 527 citations · Full text

, , +13

Least Expected Time Paths in Stochastic, Time-Varying Transportation Networks

Elise Miller-Hooks, Hani S. Mahmassani · Transportation Science · 2000 · 312 citations

, , +17

Computationally Feasible Bounds for Partially Observed Markov Decision Processes

William S. Lovejoy · Operations Research · 1991 · 310 citations

, , +17

Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators

Jaikumar Radhakrishnan, Amnon Ta‐Shma · SIAM Journal on Discrete Mathematics · 2000 · 226 citations

, , +10

1–5 of 398

Authors

735

  1. PB
    Paul Beame

    University of Washington, United States

    10 publications · 912 citations

    10

    h-index

  2. TP
    Toniann Pitassi

    University of Toronto, Canada

    8 publications · 687 citations

    8

    h-index

  3. FV
    Fedor V. Fomin

    University of Bergen, Norway

    5 publications · 229 citations

    5

    h-index

  4. SP
    Seth Pettie

    University of Michigan, United States

    5 publications · 208 citations

    5

    h-index

  5. MP
    Mihai Pǎtraşcu

    AT&T (United States), United States

    5 publications · 143 citations

    5

    h-index

1–5 of 735

Institutions

332

  1. University of California, Berkeley

    Berkeley, United States

    16 h-index

    36 publications

    1.6K citations

  2. Stanford University

    Stanford, United States

    15 h-index

    33 publications

    6.7K citations

  3. University of Washington

    Seattle, United States

    12 h-index

    22 publications

    1.4K citations

  4. Technion – Israel Institute of Technology

    Haifa, Israel

    12 h-index

    20 publications

    873 citations

  5. Massachusetts Institute of Technology

    Cambridge, United States

    11 h-index

    19 publications

    1.5K citations

  6. Princeton University

    Princeton, United States

    11 h-index

    16 publications

    990 citations

  7. Tel Aviv University

    Tel Aviv, Israel

    11 h-index

    18 publications

    685 citations

  8. University of Michigan

    Ann Arbor, United States

    10 h-index

    13 publications

    634 citations

1–8 of 332

Venues

  1. arXiv (Cornell University)

    Repository · 38 publications · 996 citations

    18

    h-index

  2. SIAM Journal on Computing

    16 publications · 805 citations

    15

    h-index

  3. Mathematical Programming

    8 publications · 449 citations

    8

    h-index

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

    Repository · 8 publications · 155 citations

    8

    h-index

  5. Journal of the ACM

    JACM · 8 publications · 512 citations

    8

    h-index

1–5