Concepedia

Computational Lower Bounds

Computational Lower Bounds is a theoretical construct in computational complexity that establishes the minimum amount of resources, such as time or space, required by any algorithm to solve a given computational problem, thereby delimiting the inherent difficulty of the problem regardless of the specific algorithmic approach employed.

636

Publications

32.2K

Citations

1.1K

Authors

475

Institutions

Publications per year

2017–2026

127

Parents

Publications

636

A Survey on TOA Based Wireless Localization and NLOS Mitigation Techniques

İsmail Güvenç, Chia‐Chin Chong · IEEE Communications Surveys & Tutorials · 2009 · 1.1K citations

, , +10

Lower bound limit analysis using finite elements and linear programming

Scott W. Sloan · International Journal for Numerical and Analytical Methods in Geomechanics · 1988 · 742 citations

, , +14

Quantum lower bounds by polynomials

Robert Beals, Harry Buhrman, Richard Cleve et al. · Journal of the ACM · 2001 · 659 citations

, , +17

Capacitated arc routing problems

Bruce Golden, Richard T. Wong · Networks · 1981 · 568 citations

, , +16

Real-time monocular SLAM: Why filter?

Hauke Strasdat, J. M. M. Montiel, Andrew J. Davison · 2010 · 460 citations

, , +15

1–5 of 636

Authors

1.1K

  1. AW
    Avi Wigderson

    Hebrew University of Jerusalem, Israel

    12 publications · 735 citations

    11

    h-index

  2. RW
    Ryan Williams

    Stanford University, United States

    11 publications · 445 citations

    10

    h-index

  3. RS
    Rahul Santhanam

    University of Oxford, United Kingdom

    8 publications · 175 citations

    8

    h-index

  4. PB
    Paul Beame

    University of Washington, United States

    8 publications · 336 citations

    8

    h-index

  5. XH
    Xiuzhen Huang

    Arkansas State University, United States

    6 publications · 613 citations

    6

    h-index

1–5 of 1.1K

Institutions

475

  1. Stanford University

    Stanford, United States

    20 h-index

    46 publications

    2K citations

  2. Massachusetts Institute of Technology

    Cambridge, United States

    18 h-index

    44 publications

    1.4K citations

  3. University of California, Berkeley

    Berkeley, United States

    17 h-index

    35 publications

    2.9K citations

  4. Princeton University

    Princeton, United States

    17 h-index

    26 publications

    1.5K citations

  5. IBM (United States)

    Armonk, United States

    13 h-index

    15 publications

    778 citations

  6. University of Washington

    Seattle, United States

    11 h-index

    22 publications

    945 citations

  7. IBM Research - Almaden

    San Jose, United States

    11 h-index

    13 publications

    1.2K citations

  8. University of California San Diego

    San Diego, United States

    11 h-index

    18 publications

    1.2K citations

1–8 of 475

Venues

  1. arXiv (Cornell University)

    Repository · 53 publications · 1.7K citations

    22

    h-index

  2. SIAM Journal on Computing

    27 publications · 1.9K citations

    21

    h-index

  3. IEEE Transactions on Information Theory

    23 publications · 2K citations

    19

    h-index

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

    Repository · 16 publications · 356 citations

    12

    h-index

  5. Journal of the ACM

    JACM · 12 publications · 1.5K citations

    11

    h-index

1–5