Concepedia

Round Complexity

Round Complexity is the measure of the minimum number of communication rounds required by a protocol to solve a given problem in the context of Communication Complexity or Secure Multi-Party Computation, distinguishing it from other complexity measures by focusing specifically on the temporal structure of interactions.

110

Publications

5.2K

Citations

214

Authors

129

Institutions

Publications per year

2017–2026

37

Parents

Publications

110

The round complexity of secure protocols

Donald Beaver, Silvio Micali, Phillip Rogaway · 1990 · 721 citations · Full text

, , +15

On the Composition of Zero-Knowledge Proof Systems

Oded Goldreich, Hugo Krawczyk · SIAM Journal on Computing · 1996 · 427 citations

, , +17

The Round Complexity of Secure Protocols (Extended Abstract)

Donald Beaver, Silvio Micali, Phillip Rogaway · Symposium on the Theory of Computing · 1990 · 200 citations

, , +15

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

1–5 of 110

Authors

214

  1. MG
    Mohsen Ghaffari

    ETH Zurich, Switzerland

    6 publications · 141 citations

    7

    h-index

  2. NN
    Noam Nisan

    Hebrew University of Jerusalem, Israel

    4 publications · 443 citations

    4

    h-index

  3. FK
    Fabian Kühn

    ETH Zurich, Switzerland

    4 publications · 119 citations

    4

    h-index

  4. BP
    Boaz Patt-Shamir

    Tel Aviv University, Israel

    4 publications · 123 citations

    4

    h-index

  5. BH
    Bernhard Haeupler

    Carnegie Mellon University, United States

    3 publications · 73 citations

    3

    h-index

1–5 of 214

Institutions

129

  1. Massachusetts Institute of Technology

    Cambridge, United States

    9 h-index

    9 publications

    1.8K citations

  2. Tel Aviv University

    Tel Aviv, Israel

    7 h-index

    11 publications

    506 citations

  3. Technion – Israel Institute of Technology

    Haifa, Israel

    6 h-index

    10 publications

    268 citations

  4. University of Maryland, College Park

    College Park, United States

    5 h-index

    7 publications

    231 citations

  5. Carnegie Mellon University

    Pittsburgh, United States

    5 h-index

    9 publications

    264 citations

  6. Weizmann Institute of Science

    Rehovot, Israel

    5 h-index

    7 publications

    466 citations

  7. ETH Zurich

    Zurich, Switzerland

    5 h-index

    5 publications

    73 citations

  8. Microsoft (United States)

    Redmond, United States

    4 h-index

    5 publications

    122 citations

1–8 of 129

Venues

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

    Repository · 7 publications · 103 citations

    7

    h-index

  2. SIAM Journal on Computing

    5 publications · 681 citations

    5

    h-index

  3. arXiv (Cornell University)

    Repository · 5 publications · 67 citations

    5

    h-index

  4. IEEE Transactions on Parallel and Distributed Systems

    TPDS · 4 publications · 103 citations

    4

    h-index

  5. Proceedings on Privacy Enhancing Technologies

    PoPETs · 3 publications · 106 citations

    4

    h-index

1–5