Concepedia

Deterministic Communication Complexity

Deterministic Communication Complexity is the minimum number of bits that must be exchanged between two deterministic parties in a communication model to compute a function whose inputs are distributed between them, distinguishing it from probabilistic or nondeterministic variants by requiring exact computation without randomness or error.

43

Publications

1.9K

Citations

63

Authors

36

Institutions

Publications per year

2017–2026

4

Parents

Publications

43

Rounds in Communication Complexity Revisited

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

, , +17

Communication complexity of common voting rules

Vincent Conitzer, Tüomas Sandholm · 2005 · 137 citations · Full text

, , +17

On the time-complexity of broadcast in radio networks: an exponential gap between determinism randomization

Reuven Bar-Yehuda, Oded Goldreich, Alon Itai · 1987 · 124 citations

, , +17

Nonlocality Distillation and Postquantum Theories with Trivial Communication Complexity

Nicolas Brunner, Paul Skrzypczyk · Physical Review Letters · 2009 · 122 citations · Full text

, , +9

Amortized Communication Complexity

Tomás Feder, Eyal Kushilevitz, Moni Naor et al. · SIAM Journal on Computing · 1995 · 119 citations

, , +16

1–5 of 43

Authors

63

  1. EK
    Eyal Kushilevitz

    Technion – Israel Institute of Technology, Israel

    6 publications · 252 citations

    6

    h-index

  2. NN
    Noam Nisan

    Hebrew University of Jerusalem, Israel

    6 publications · 467 citations

    6

    h-index

  3. SL
    Shachar Lovett

    University of California San Diego, United States

    4 publications · 78 citations

    4

    h-index

  4. RK
    Robin Kothari

    University of Waterloo, Canada

    2 publications · 41 citations

    2

    h-index

  5. AE
    Abbas El Gamal

    Stanford University, United States

    2 publications · 74 citations

    2

    h-index

1–5 of 63

Institutions

36

  1. Technion – Israel Institute of Technology

    Haifa, Israel

    6 h-index

    12 publications

    509 citations

  2. Hebrew University of Jerusalem

    Jerusalem, Israel

    5 h-index

    7 publications

    293 citations

  3. Stanford University

    Stanford, United States

    3 h-index

    4 publications

    159 citations

  4. University of California San Diego

    San Diego, United States

    3 h-index

    6 publications

    134 citations

  5. McGill University

    Montreal, Canada

    2 h-index

    4 publications

    106 citations

  6. Tsinghua University

    Beijing, China

    2 h-index

    2 publications

    52 citations

  7. Sun Yat-sen University

    Guangzhou, China

    2 h-index

    3 publications

    74 citations

  8. AT&T (United States)

    Bedminster, United States

    2 h-index

    2 publications

    46 citations

1–8 of 36

Venues

  1. SIAM Journal on Computing

    6 publications · 399 citations

    6

    h-index

  2. arXiv (Cornell University)

    Repository · 3 publications · 61 citations

    3

    h-index

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

    Repository · 2 publications · 32 citations

    2

    h-index

  4. Discrete Applied Mathematics

    1 publications · 12 citations

    1

    h-index

  5. Review of Communication Research

    1 publications · 35 citations

    1

    h-index

1–5