Concepedia

Smoothed Complexity

Smoothed Complexity is a computational complexity measure that belongs to the class of hybrid analysis frameworks, differing from worst-case and average-case analyses by evaluating the expected performance of algorithms under slight random perturbations of worst-case inputs.

20

Publications

1.2K

Citations

39

Authors

25

Institutions

Publications per year

2017–2026

1

Parents

Publications

20

Settling the complexity of computing two-player Nash equilibria

Xi Chen, Xiaotie Deng, Shang‐Hua Teng · Journal of the ACM · 2009 · 579 citations

, , +17

k-Means Has Polynomial Smoothed Complexity

David Arthur, Bodo Manthey, Heiko Röglin · 2009 · 104 citations · Full text

, , +13

On a problem posed by Steve Smale

Peter Bürgisser, Felipe Cucker · Annals of Mathematics · 2011 · 77 citations · Full text

, , +16

Smoothed analysis of the perceptron algorithm for linear programming

Avrim Blum, John Dunagan · Research Showcase @ Carnegie Mellon University (Carnegie Mellon University) · 2002 · 66 citations

, , +16

Typical Properties of Winners and Losers [0.2ex] in Discrete Optimization

René Beier, Berthold Vöcking · SIAM Journal on Computing · 2006 · 58 citations

, , +17

1–5 of 20

Authors

39

  1. ST
    Shang‐Hua Teng

    University of Southern California, United States

    6 publications · 714 citations

    6

    h-index

  2. DA
    Daniel A. Spielman

    Yale University, United States

    3 publications · 100 citations

    3

    h-index

  3. HR
    Heiko Röglin

    University of Bonn, Germany

    3 publications · 155 citations

    3

    h-index

  4. DA
    David Arthur

    Stanford University, United States

    2 publications · 119 citations

    2

    h-index

  5. BM
    Bodo Manthey

    University of Twente, Netherlands

    2 publications · 119 citations

    2

    h-index

1–5 of 39

Institutions

25

  1. Boston University

    Boston, United States

    4 h-index

    4 publications

    666 citations

  2. Microsoft (United States)

    Redmond, United States

    4 h-index

    5 publications

    122 citations

  3. Stanford University

    Stanford, United States

    4 h-index

    5 publications

    172 citations

  4. Maastricht University

    Maastricht, The Netherlands

    3 h-index

    3 publications

    155 citations

  5. Tsinghua University

    Beijing, China

    3 h-index

    3 publications

    604 citations

  6. City University of Hong Kong

    Hong Kong, Hong Kong

    3 h-index

    3 publications

    668 citations

  7. Massachusetts Institute of Technology

    Cambridge, United States

    3 h-index

    3 publications

    146 citations

  8. Akamai (United States)

    Cambridge, United States

    3 h-index

    3 publications

    646 citations

1–8 of 25

Venues

  1. arXiv (Cornell University)

    Repository · 2 publications · 85 citations

    2

    h-index

  2. Evolutionary Computation

    1 publications · 27 citations

    1

    h-index

  3. SIAM Journal on Computing

    1 publications · 58 citations

    1

    h-index

  4. Mathematical Programming

    1 publications · 20 citations

    1

    h-index

  5. ACM Transactions on Algorithms

    TALG · 1 publications · 13 citations

    1

    h-index

1–5