Concepedia

Worst-case Complexity

Worst-Case Complexity is the asymptotic upper bound on the computational resource usage of an algorithm, defined as the maximum number of steps required over all possible inputs of a given size, distinguishing it from average-case or best-case analyses by focusing on the most unfavorable input scenario.

1.2K

Publications

72.4K

Citations

2.2K

Authors

736

Institutions

Publications per year

2017–2026

163

Parents

Publications

1.2K

Semidefinite Programming

Lieven Vandenberghe, Stephen Boyd · SIAM Review · 1996 · 4.1K citations

, , +11

Feature selection, <i>L</i><sub>1</sub> vs. <i>L</i><sub>2</sub> regularization, and rotational invariance

Andrew Y. Ng · 2004 · 1.6K citations

, , +16

Efficient Fully Homomorphic Encryption from (Standard) LWE

Zvika Brakerski, Vinod Vaikuntanathan · 2011 · 1.5K citations

, , +15

On the sphere-decoding algorithm I. Expected complexity

Babak Hassibi, Haris Vikalo · IEEE Transactions on Signal Processing · 2005 · 1.2K citations

, , +14

Complexity of Finding Embeddings in a <i>k</i>-Tree

Stefan Arnborg, Derek G. Corneil, Andrzej Proskurowski · SIAM Journal on Algebraic and Discrete Methods · 1987 · 1.2K citations

, , +15

1–5 of 1.2K

Authors

2.2K

  1. CC
    Coralia Cartis

    University of Oxford, United Kingdom

    10 publications · 476 citations

    10

    h-index

  2. LN
    L. N. Vicente

    University of Coimbra, Portugal

    7 publications · 373 citations

    7

    h-index

  3. PL
    Philippe L. Toint

    University of Namur, Belgium

    7 publications · 489 citations

    7

    h-index

  4. NI
    Nicholas I. M. Gould

    Rutherford Appleton Laboratory, United Kingdom

    7 publications · 364 citations

    7

    h-index

  5. LT
    Luca Trevisan

    University of California, Berkeley, United States

    6 publications · 476 citations

    6

    h-index

1–5 of 2.2K

Institutions

736

  1. University of California, Berkeley

    Berkeley, United States

    27 h-index

    45 publications

    3.9K citations

  2. Massachusetts Institute of Technology

    Cambridge, United States

    25 h-index

    53 publications

    3.2K citations

  3. Stanford University

    Stanford, United States

    19 h-index

    37 publications

    3.5K citations

  4. Carnegie Mellon University

    Pittsburgh, United States

    17 h-index

    26 publications

    2K citations

  5. Columbia University

    New York, United States

    17 h-index

    23 publications

    1.8K citations

  6. University of California San Diego

    San Diego, United States

    15 h-index

    32 publications

    3.1K citations

  7. Microsoft (United States)

    Redmond, United States

    15 h-index

    19 publications

    1.2K citations

  8. University of Minnesota

    Minneapolis, United States

    15 h-index

    21 publications

    1.6K citations

1–8 of 736

Venues

  1. SIAM Journal on Computing

    58 publications · 6.9K citations

    38

    h-index

  2. arXiv (Cornell University)

    Repository · 40 publications · 1.1K citations

    20

    h-index

  3. SIAM Journal on Optimization

    22 publications · 1K citations

    19

    h-index

  4. Journal of the ACM

    JACM · 19 publications · 3.4K citations

    18

    h-index

  5. Mathematical Programming

    16 publications · 985 citations

    13

    h-index

1–5