Concepedia

Randomized Local Computation

Randomized Local Computation is a computational paradigm in randomized complexity theory that characterizes algorithms which, given a query about a specific part of the output, produce a localized response by performing randomized computations on a small portion of the input, ensuring consistency with a global solution while adhering to strict bounds on time and space resources.

23

Publications

1.1K

Citations

43

Authors

23

Institutions

Publications per year

2017–2026

3

Variants

Local Computation Algorithms

Parents

Publications

23

What Can be Computed Locally?

Moni Naor, Larry Stockmeyer · SIAM Journal on Computing · 1995 · 317 citations

, , +12

Towards a complexity theory for local distributed computing

Pierre Fraigniaud, Amos Korman, David Peleg · Journal of the ACM · 2013 · 116 citations

, , +14

What can be computed locally?

Moni Naor, Larry Stockmeyer · 1993 · 108 citations

, , +12

Fast Local Computation Algorithms

Ronitt Rubinfeld, Gil Tamir, Shai Vardi et al. · arXiv (Cornell University) · 2011 · 54 citations · Full text

, , +15

Local MST Computation with Short Advice

Pierre Fraigniaud, Amos Korman, Emmanuelle Lebhar · Theory of Computing Systems · 2010 · 54 citations

, , +3

1–5 of 23

Authors

43

  1. AK
    Amos Korman

    Centre National de la Recherche Scientifique, France

    3 publications · 205 citations

    3

    h-index

  2. RR
    Ronitt Rubinfeld

    Massachusetts Institute of Technology, United States

    3 publications · 88 citations

    3

    h-index

  3. PF
    Pierre Fraigniaud

    Centre National de la Recherche Scientifique, France

    3 publications · 184 citations

    3

    h-index

  4. LS
    Larry Stockmeyer

    IBM Research - Almaden, United States

    2 publications · 425 citations

    2

    h-index

  5. AY
    Anak Yodpinyanee

    Tel Aviv University, Israel

    2 publications · 34 citations

    2

    h-index

1–5 of 43

Institutions

23

  1. Université Paris Cité

    Paris, France

    6 h-index

    10 publications

    512 citations

  2. Centre National de la Recherche Scientifique

    Paris, France

    4 h-index

    8 publications

    478 citations

  3. Délégation Paris 7

    Bagnolet, France

    4 h-index

    5 publications

    280 citations

  4. Weizmann Institute of Science

    Rehovot, Israel

    4 h-index

    4 publications

    262 citations

  5. Massachusetts Institute of Technology

    Cambridge, United States

    3 h-index

    6 publications

    162 citations

  6. Tel Aviv University

    Tel Aviv, Israel

    3 h-index

    3 publications

    103 citations

  7. Technion – Israel Institute of Technology

    Haifa, Israel

    3 h-index

    3 publications

    100 citations

  8. Laboratoire d'Informatique Algorithmique: Fondements et Applications

    Paris, France

    2 h-index

    3 publications

    122 citations

1–8 of 23

Venues

  1. SIAM Journal on Computing

    3 publications · 384 citations

    3

    h-index

  2. 1

    h-index

  3. Journal of the ACM

    JACM · 1 publications · 116 citations

    1

    h-index

  4. Computational Complexity

    CC · 1 publications · 32 citations

    1

    h-index

  5. arXiv (Cornell University)

    Repository · 1 publications · 54 citations

    1

    h-index

1–5