Concepedia

Randomized Time Complexity

Randomized Time Complexity is a computational complexity measure that characterizes the asymptotic time required by a randomized algorithm to solve a problem, distinguished from deterministic time complexity by incorporating probabilistic transitions and expected or high-probability performance bounds over random choices made during execution.

55

Publications

2.7K

Citations

107

Authors

72

Institutions

Publications per year

2017–2026

6

Parents

Publications

55

On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization

Reuven Bar-Yehuda, Oded Goldreich, Alon Itai · Journal of Computer and System Sciences · 1992 · 434 citations

, , +14

A randomized linear-time algorithm to find minimum spanning trees

David R. Karger, Philip N. Klein, Robert E. Tarjan · Journal of the ACM · 1995 · 404 citations · Full text

, , +14

Time complexity of evolutionary algorithms for combinatorial optimization: A decade of results

Pietro S. Oliveto, Jun He, Xin Yao · International Journal of Automation and Computing · 2007 · 221 citations

, , +14

Maximal independent sets in radio networks

Thomas Moscibroda, Rogert Wattenhofer · 2005 · 125 citations

, , +16

A Bluetooth scatternet formation algorithm

Ching Law, Kai‐Yeung Siu · 2002 · 108 citations

, , +17

1–5 of 55

Authors

107

  1. KE
    Klim Efremenko

    Carnegie Mellon University, United States

    2 publications · 38 citations

    2

    h-index

  2. EC
    Edith Cohen

    AT&T (United States), United States

    2 publications · 73 citations

    2

    h-index

  3. JC
    Joseph Cheriyan

    University of Waterloo, Canada

    2 publications · 40 citations

    2

    h-index

  4. DR
    Dariusz R. Kowalski

    University of Liverpool, United Kingdom

    2 publications · 101 citations

    2

    h-index

  5. AP
    Andrzej Pelc

    Université du Québec en Outaouais, Canada

    2 publications · 101 citations

    2

    h-index

1–5 of 107

Institutions

72

  1. Stanford University

    Stanford, United States

    5 h-index

    6 publications

    481 citations

  2. Massachusetts Institute of Technology

    Cambridge, United States

    4 h-index

    8 publications

    324 citations

  3. Max Planck Society

    Munich, Germany

    3 h-index

    3 publications

    100 citations

  4. Tel Aviv University

    Tel Aviv, Israel

    3 h-index

    5 publications

    203 citations

  5. Weizmann Institute of Science

    Rehovot, Israel

    2 h-index

    2 publications

    55 citations

  6. Lund University

    Lund, Sweden

    2 h-index

    2 publications

    30 citations

  7. Harvard University

    Cambridge, United States

    2 h-index

    4 publications

    48 citations

  8. IBM (United States)

    Armonk, United States

    2 h-index

    3 publications

    92 citations

1–8 of 72

Venues

  1. SIAM Journal on Computing

    8 publications · 296 citations

    8

    h-index

  2. Journal of Computer and System Sciences

    2 publications · 486 citations

    2

    h-index

  3. Journal of Complexity

    2 publications · 60 citations

    2

    h-index

  4. Computational Statistics & Data Analysis

    CSDA · 1 publications · 11 citations

    1

    h-index

  5. 1

    h-index

1–5