Concepedia

Derandomization

Derandomization is a theoretical framework in computational complexity that characterizes the systematic reduction or elimination of randomness in algorithms while preserving their correctness and efficiency, distinguishing it from alternative approaches by its focus on converting probabilistic computation into deterministic computation under resource constraints.

175

Publications

7.9K

Citations

279

Authors

135

Institutions

Publications per year

2017–2026

30

Parents

Publications

175

Pseudorandom Generators without the XOR Lemma

Madhu Sudan, Luca Trevisan, Salil Vadhan · Journal of Computer and System Sciences · 2001 · 406 citations · Full text

, , +16

Linear degree extractors and the inapproximability of max clique and chromatic number

David Zuckerman · 2006 · 404 citations

, , +16

The discrepancy method: randomness and complexity

Choice Reviews Online · 2002 · 365 citations

, , +16

Splitters and near-optimal derandomization

Moni Naor, Leonard J. Schulman, A. Srinivasan · 2002 · 306 citations

, , +13

In search of an easy witness: exponential time vs. probabilistic polynomial time

Russell Impagliazzo, Valentine Kabanets, Avi Wigderson · Journal of Computer and System Sciences · 2002 · 214 citations

, , +17

1–5 of 175

Authors

279

  1. AW
    Avi Wigderson

    Hebrew University of Jerusalem, Israel

    14 publications · 952 citations

    13

    h-index

  2. SV
    Salil Vadhan

    Harvard University Press, United States

    10 publications · 729 citations

    10

    h-index

  3. RI
    Russell Impagliazzo

    University of California San Diego, United States

    8 publications · 619 citations

    8

    h-index

  4. MS
    Madhu Sudan

    Massachusetts Institute of Technology, United States

    7 publications · 666 citations

    7

    h-index

  5. LT
    Luca Trevisan

    University of California, Berkeley, United States

    4 publications · 500 citations

    4

    h-index

1–5 of 279

Institutions

135

  1. Stanford University

    Stanford, United States

    13 h-index

    20 publications

    789 citations

  2. Tel Aviv University

    Tel Aviv, Israel

    11 h-index

    14 publications

    649 citations

  3. Harvard University

    Cambridge, United States

    11 h-index

    15 publications

    955 citations

  4. Weizmann Institute of Science

    Rehovot, Israel

    11 h-index

    14 publications

    1K citations

  5. Hebrew University of Jerusalem

    Jerusalem, Israel

    9 h-index

    10 publications

    841 citations

  6. Massachusetts Institute of Technology

    Cambridge, United States

    9 h-index

    10 publications

    824 citations

  7. University of California San Diego

    San Diego, United States

    8 h-index

    9 publications

    793 citations

  8. Institute for Advanced Study

    Princeton, United States

    6 h-index

    7 publications

    398 citations

1–8 of 135

Venues

  1. SIAM Journal on Computing

    12 publications · 521 citations

    12

    h-index

  2. arXiv (Cornell University)

    Repository · 6 publications · 81 citations

    6

    h-index

  3. Computational Complexity

    CC · 5 publications · 147 citations

    5

    h-index

  4. Journal of Computer and System Sciences

    3 publications · 721 citations

    3

    h-index

  5. Random Structures and Algorithms

    3 publications · 77 citations

    3

    h-index

1–5