Concepedia

Randomized Communication Complexity

Randomized Communication Complexity is a measure in computational complexity theory that quantifies the minimum amount of communication required between two parties to compute a function with high probability, using randomized protocols, where the randomness may depend on both inputs and public/private coins.

67

Publications

3.9K

Citations

96

Authors

68

Institutions

Publications per year

2017–2026

4

Parents

Publications

67

On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization

Reuven Bar-Yehuda, Oded Goldreich, Alon Itai · Journal of Computer and System Sciences · 1992 · 434 citations

, , +14

The discrepancy method: randomness and complexity

Choice Reviews Online · 2002 · 365 citations

, , +16

On Randomized One-round Communication Complexity

Ilan Kremer, Noam Nisan, Dorit Ron · Computational Complexity · 1999 · 174 citations

, , +13

Rounds in Communication Complexity Revisited

Noam Nisan, Avi Wigderson · SIAM Journal on Computing · 1993 · 169 citations

, , +17

Randomized Byzantine Agreements

Sam Toueg · 1984 · 156 citations

, , +15

1–5 of 67

Authors

96

  1. HK
    Hartmut Klauck

    Centre for Quantum Technologies, Singapore

    5 publications · 262 citations

    5

    h-index

  2. RJ
    Rahul Jain

    National University of Singapore, Singapore

    5 publications · 169 citations

    5

    h-index

  3. MB
    Mark Braverman

    Princeton University, United States

    5 publications · 292 citations

    5

    h-index

  4. TS
    T. S. Jayram

    IBM Research - Almaden, United States

    5 publications · 194 citations

    5

    h-index

  5. QZ
    Qin Zhang

    Indiana University Bloomington, United States

    4 publications · 168 citations

    4

    h-index

1–5 of 96

Institutions

68

  1. University of Washington

    Seattle, United States

    8 h-index

    10 publications

    364 citations

  2. Hebrew University of Jerusalem

    Jerusalem, Israel

    6 h-index

    11 publications

    757 citations

  3. Université Paris Cité

    Paris, France

    5 h-index

    7 publications

    213 citations

  4. University of Toronto

    Toronto, Canada

    5 h-index

    6 publications

    241 citations

  5. Princeton University

    Princeton, United States

    4 h-index

    6 publications

    296 citations

  6. National University of Singapore

    Singapore, Singapore

    4 h-index

    10 publications

    226 citations

  7. Stanford University

    Stanford, United States

    4 h-index

    5 publications

    200 citations

  8. Centre for Quantum Technologies

    Singapore, Singapore

    4 h-index

    7 publications

    307 citations

1–8 of 68

Venues

  1. SIAM Journal on Computing

    8 publications · 409 citations

    8

    h-index

  2. Computational Complexity

    CC · 4 publications · 368 citations

    4

    h-index

  3. DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)

    Repository · 4 publications · 60 citations

    4

    h-index

  4. arXiv (Cornell University)

    Repository · 3 publications · 44 citations

    3

    h-index

  5. ArXiv.org

    Repository · 2 publications · 87 citations

    2

    h-index

1–5