Concepedia

Randomized Complexity Theory

Randomized Complexity Theory is a branch of computational complexity theory that studies the classification of computational problems according to their inherent difficulty under models of computation that allow randomized algorithms, distinguished by its focus on probabilistic Turing machines and complexity classes such as BPP, RP, and ZPP.

266

Publications

15.9K

Citations

386

Authors

195

Institutions

Publications per year

2017–2026

24

Parents

Publications

266

The Space Complexity of Approximating the Frequency Moments

Noga Alon, Yossi Matias, Márió Szegedy · Journal of Computer and System Sciences · 1999 · 1.2K citations

, , +15

The space complexity of approximating the frequency moments

Noga Alon, Yossi Matias, Márió Szegedy · 1996 · 847 citations

, , +15

Trading group theory for randomness

László Babai · 1985 · 782 citations

, , +8

IP = PSPACE

Adi Shamir · Journal of the ACM · 1992 · 657 citations · Full text

, , +14

Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes

László Babai, Shlomo Moran · Journal of Computer and System Sciences · 1988 · 596 citations

, , +16

1–5 of 266

Authors

386

  1. AW
    Avi Wigderson

    Hebrew University of Jerusalem, Israel

    10 publications · 410 citations

    10

    h-index

  2. SP
    Seth Pettie

    University of Michigan, United States

    8 publications · 538 citations

    8

    h-index

  3. CL
    Carsten Lund

    AT&T (United States), United States

    6 publications · 117 citations

    6

    h-index

  4. LT
    Luca Trevisan

    University of California, Berkeley, United States

    6 publications · 615 citations

    6

    h-index

  5. HK
    Hartmut Klauck

    Centre for Quantum Technologies, Singapore

    6 publications · 281 citations

    6

    h-index

1–5 of 386

Institutions

195

  1. Princeton University

    Princeton, United States

    11 h-index

    18 publications

    768 citations

  2. Weizmann Institute of Science

    Rehovot, Israel

    10 h-index

    10 publications

    939 citations

  3. Tel Aviv University

    Tel Aviv, Israel

    10 h-index

    10 publications

    1.2K citations

  4. Massachusetts Institute of Technology

    Cambridge, United States

    10 h-index

    17 publications

    809 citations

  5. University of California, Berkeley

    Berkeley, United States

    10 h-index

    11 publications

    647 citations

  6. ETH Zurich

    Zurich, Switzerland

    10 h-index

    13 publications

    864 citations

  7. University of Washington

    Seattle, United States

    9 h-index

    16 publications

    577 citations

  8. University of Chicago

    Chicago, United States

    9 h-index

    11 publications

    1.7K citations

1–8 of 195

Venues

  1. SIAM Journal on Computing

    27 publications · 2K citations

    19

    h-index

  2. arXiv (Cornell University)

    Repository · 11 publications · 312 citations

    10

    h-index

  3. Theoretical Computer Science

    9 publications · 198 citations

    9

    h-index

  4. Journal of the ACM

    JACM · 7 publications · 1.1K citations

    7

    h-index

  5. Journal of Computer and System Sciences

    7 publications · 2.4K citations

    7

    h-index

1–5