Concepedia

Nondeterministic Communication Complexity

Nondeterministic Communication Complexity is a measure in communication complexity theory that characterizes the minimum number of bits that two parties must exchange, in the presence of a nondeterministic proof, to verify the value of a function when each party knows only one part of the input.

49

Publications

4.6K

Citations

94

Authors

61

Institutions

Publications per year

2017–2026

4

Parents

Publications

49

HotStuff

Maofan Yin, Dahlia Malkhi, Michael K. Reiter et al. · 2019 · 944 citations · Full text

, , +17

A secure and optimally efficient multi‐authority election scheme

Ronald Cramer, Rosario Gennaro, Berry Schoenmakers · European Transactions on Telecommunications · 1997 · 790 citations

, , +13

The Probabilistic Communication Complexity of Set Intersection

Bala Kalyanasundaram, Georg Schintger · SIAM Journal on Discrete Mathematics · 1992 · 458 citations

, , +13

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 complexity of the generalized Lloyd - Max problem (Corresp.)

M. R. Garey, David S. Johnson, H. S. Witsenhausen · IEEE Transactions on Information Theory · 1982 · 188 citations

, , +13

1–5 of 49

Authors

94

  1. HK
    Hartmut Klauck

    Centre for Quantum Technologies, Singapore

    5 publications · 248 citations

    5

    h-index

  2. DD
    Danny Dolev

    Hebrew University of Jerusalem, Israel

    4 publications · 139 citations

    4

    h-index

  3. JH
    Juraj Hromkovic̆

    ETH Zurich, Switzerland

    4 publications · 132 citations

    4

    h-index

  4. MK
    Mauricio Karchmer

    Hebrew University of Jerusalem, Israel

    3 publications · 111 citations

    3

    h-index

  5. IA
    Ittai Abraham

    Hebrew University of Jerusalem, Israel

    3 publications · 1K citations

    3

    h-index

1–5 of 94

Institutions

61

  1. Technion – Israel Institute of Technology

    Haifa, Israel

    4 h-index

    8 publications

    1.4K citations

  2. Hebrew University of Jerusalem

    Jerusalem, Israel

    4 h-index

    4 publications

    142 citations

  3. University of Illinois Urbana-Champaign

    Urbana, United States

    3 h-index

    5 publications

    113 citations

  4. Centrum Wiskunde & Informatica

    Amsterdam, The Netherlands

    3 h-index

    3 publications

    116 citations

  5. Cornell University

    Ithaca, United States

    3 h-index

    4 publications

    1.1K citations

  6. Adolfo Ibáñez University

    Santiago, Chile

    2 h-index

    2 publications

    47 citations

  7. University of Turku

    Turku, Finland

    2 h-index

    3 publications

    110 citations

  8. Stanford University

    Stanford, United States

    2 h-index

    2 publications

    47 citations

1–8 of 61

Venues

  1. SIAM Journal on Computing

    5 publications · 159 citations

    5

    h-index

  2. Theoretical Computer Science

    5 publications · 178 citations

    5

    h-index

  3. Journal of Computer and System Sciences

    3 publications · 645 citations

    3

    h-index

  4. 2

    h-index

  5. ArXiv.org

    Repository · 2 publications · 61 citations

    2

    h-index

1–5