Concepedia

Randomized Reductions

Randomized Reductions is a computational method in randomized complexity theory that transforms one problem into another with bounded error probability, distinguishing it from deterministic reductions by incorporating randomness to achieve correctness with high probability.

39

Publications

2.4K

Citations

57

Authors

41

Institutions

Publications per year

2017–2026

4

Parents

Publications

39

The shortest vector problem in <i>L<sub>2</sub></i> is <i>NP</i>-hard for randomized reductions (extended abstract)

Miklós Ajtai · 1998 · 403 citations

, , +12

Splitters and near-optimal derandomization

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

, , +13

The Shortest Vector Problem in L 2 is NP-hard for Randomized Reductions.

Miklós Ajtai · Electronic colloquium on computational complexity · 1997 · 248 citations

, , +11

The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant

Daniele Micciancio · SIAM Journal on Computing · 2001 · 207 citations

, , +12

On the Hardness of Graph Isomorphism

Jacobo Torán · SIAM Journal on Computing · 2004 · 107 citations

, , +17

1–5 of 39

Authors

57

  1. PR
    Pankaj Rohatgi

    IBM (United States), United States

    4 publications · 67 citations

    4

    h-index

  2. SP
    Seth Pettie

    University of Michigan, United States

    3 publications · 145 citations

    3

    h-index

  3. DM
    Daniele Micciancio

    University of California San Diego, United States

    2 publications · 296 citations

    2

    h-index

  4. SD
    Shaddin Dughmi

    University of Southern California, United States

    2 publications · 76 citations

    2

    h-index

  5. EP
    Ely Porat

    Bar-Ilan University, Israel

    2 publications · 127 citations

    2

    h-index

1–5 of 57

Institutions

41

  1. Cornell University

    Ithaca, United States

    4 h-index

    8 publications

    147 citations

  2. University of Michigan

    Ann Arbor, United States

    3 h-index

    6 publications

    332 citations

  3. University of California, Irvine

    Irvine, United States

    3 h-index

    4 publications

    139 citations

  4. University at Buffalo, State University of New York

    Buffalo, United States

    2 h-index

    4 publications

    144 citations

  5. Bar-Ilan University

    Ramat Gan, Israel

    2 h-index

    4 publications

    247 citations

  6. IBM Research - Almaden

    San Jose, United States

    2 h-index

    2 publications

    414 citations

  7. University of Maine

    Orono, United States

    2 h-index

    6 publications

    114 citations

  8. California Institute of Technology

    Pasadena, United States

    2 h-index

    2 publications

    63 citations

1–8 of 41

Venues

  1. SIAM Journal on Computing

    6 publications · 427 citations

    6

    h-index

  2. Journal of Computer and System Sciences

    4 publications · 124 citations

    4

    h-index

  3. IEEE Transactions on Information Theory

    2 publications · 125 citations

    2

    h-index

  4. Symposium on Discrete Algorithms

    Conference · 1 publications · 67 citations

    1

    h-index

  5. Quantum

    1 publications · 23 citations

    1

    h-index

1–5