Randomized Complexity

Randomized Complexity is a subfield of computational complexity theory that analyzes the computational resources needed by randomized algorithms or probabilistic Turing machines to solve decision and function problems with specified bounds on running time and error probability, typically formalized via probabilistic complexity classes such as BPP, RP, and ZPP.

1.3K

Publications

72.7K

Citations

1.6K

Authors

541

Institutions

Publications per year

2017–2026

134

Authors

1.6K

  1. AW
    Avi Wigderson

    Hebrew University of Jerusalem, Israel

    23 publications · 1.2K citations

    19

    h-index

  2. RI
    Russell Impagliazzo

    University of California San Diego, United States

    15 publications · 1.3K citations

    15

    h-index

  3. NA
    Noga Alon

    Tel Aviv University, Israel

    15 publications · 3.8K citations

    14

    h-index

  4. RA
    Rocco A. Servedio

    Columbia University, United States

    19 publications · 797 citations

    13

    h-index

  5. PB
    Paul Beame

    University of Washington, United States

    15 publications · 643 citations

    13

    h-index

1–5 of 1.6K

Venues

  1. SIAM Journal on Computing

    114 publications · 7.4K citations

    48

    h-index

  2. Theoretical Computer Science

    55 publications · 2.4K citations

    28

    h-index

  3. Journal of Computer and System Sciences

    35 publications · 4.1K citations

    26

    h-index

  4. Journal of the ACM

    JACM · 28 publications · 3.9K citations

    24

    h-index

  5. Computational Complexity

    CC · 30 publications · 2.1K citations

    21

    h-index

1–5