Concepedia

Average-case Complexity

Average-Case Complexity is a computational complexity measure that characterizes the expected resource consumption of an algorithm over all possible inputs of a given size, under a specified probability distribution, distinguishing it from worst-case and best-case complexity measures by focusing on typical rather than extremal input behavior.

237

Publications

11.3K

Citations

393

Authors

214

Institutions

Publications per year

2017–2026

28

Parents

Publications

237

Maximal vector computation in large data sets

Parke Godfrey, J. Ryan Shipley, Jarek Gryz · 2005 · 373 citations

, , +15

Relations between average case complexity and approximation complexity

Uriel Feige · 2002 · 370 citations

, , +14

Graph bisection algorithms with good average case behavior

Thanh‐Tung Bui, S.K. Chaudhuri, F. T. Leighton et al. · COMBINATORICA · 1987 · 327 citations

, , +8

Average-Case Complexity Versus Approximate Simulation of Commuting Quantum Computations

Michael J. Bremner, Ashley Montanaro, Dan Shepherd · Physical Review Letters · 2016 · 312 citations · Full text

, , +17

A personal view of average-case complexity

Russell Impagliazzo · 2002 · 298 citations

, , +15

1–5 of 237

Authors

393

  1. LT
    Luca Trevisan

    University of California, Berkeley, United States

    6 publications · 476 citations

    6

    h-index

  2. HW
    H. Woźniakowski

    University of Warsaw, Poland

    6 publications · 421 citations

    6

    h-index

  3. PW
    Peter W. Shor

    AT&T (United States), United States

    5 publications · 322 citations

    5

    h-index

  4. OG
    Oded Goldreich

    Weizmann Institute of Science, Israel

    5 publications · 283 citations

    5

    h-index

  5. JC
    Jin‐Yi Cai

    University of Wisconsin–Madison, United States

    4 publications · 116 citations

    4

    h-index

1–5 of 393

Institutions

214

  1. Massachusetts Institute of Technology

    Cambridge, United States

    12 h-index

    17 publications

    2K citations

  2. Columbia University

    New York, United States

    11 h-index

    16 publications

    685 citations

  3. University of California, Berkeley

    Berkeley, United States

    9 h-index

    13 publications

    966 citations

  4. University of Warsaw

    Warsaw, Poland

    8 h-index

    9 publications

    392 citations

  5. Hebrew University of Jerusalem

    Jerusalem, Israel

    8 h-index

    13 publications

    883 citations

  6. University of California, Los Angeles

    Los Angeles, United States

    7 h-index

    9 publications

    334 citations

  7. Max Planck Institute for Informatics

    Saarbrücken, Germany

    7 h-index

    7 publications

    225 citations

  8. Max Planck Society

    Munich, Germany

    6 h-index

    7 publications

    251 citations

1–8 of 214

Venues

  1. SIAM Journal on Computing

    12 publications · 743 citations

    11

    h-index

  2. Journal of Complexity

    12 publications · 421 citations

    11

    h-index

  3. arXiv (Cornell University)

    Repository · 11 publications · 506 citations

    10

    h-index

  4. Theoretical Computer Science

    4 publications · 58 citations

    4

    h-index

  5. Information Processing Letters

    4 publications · 123 citations

    4

    h-index

1–5