Concepedia

Communication Complexity Of Boolean Functions

The Communication Complexity of Boolean Functions is a computational complexity measure that quantifies the minimum amount of communication required between two or more parties to compute a Boolean function whose input is distributed among them, distinguishing it from other complexity measures by focusing specifically on the information exchange necessary to evaluate the function correctly.

70

Publications

3.7K

Citations

97

Authors

59

Institutions

Publications per year

2017–2026

2

Parents

Publications

70

Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity

Benny Chor, Oded Goldreich · SIAM Journal on Computing · 1988 · 558 citations

, , +10

Informational complexity and the direct sum problem for simultaneous message complexity

Amit Chakrabarti, Yaoyun Shi, Anthony Wirth et al. · 2001 · 265 citations

, , +15

Lower bounds by probabilistic arguments

Andrew Chi-Chih Yao · 1983 · 213 citations

, , +17

On rank vs. communication complexity

Noam Nisan, Avi Wigderson · COMBINATORICA · 1995 · 142 citations

, , +14

Amortized Communication Complexity

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

, , +16

1–5 of 70

Authors

97

  1. EK
    Eyal Kushilevitz

    Technion – Israel Institute of Technology, Israel

    5 publications · 194 citations

    5

    h-index

  2. AW
    Avi Wigderson

    Hebrew University of Jerusalem, Israel

    5 publications · 331 citations

    5

    h-index

  3. HK
    Hartmut Klauck

    Centre for Quantum Technologies, Singapore

    5 publications · 219 citations

    5

    h-index

  4. SL
    Shachar Lovett

    University of California San Diego, United States

    5 publications · 191 citations

    5

    h-index

  5. AA
    Alexander A. Sherstov

    The University of Texas at Austin, United States

    4 publications · 164 citations

    4

    h-index

1–5 of 97

Institutions

59

  1. Centrum Wiskunde & Informatica

    Amsterdam, The Netherlands

    7 h-index

    7 publications

    283 citations

  2. The University of Texas at Austin

    Austin, United States

    6 h-index

    6 publications

    278 citations

  3. Technion – Israel Institute of Technology

    Haifa, Israel

    4 h-index

    5 publications

    141 citations

  4. Hebrew University of Jerusalem

    Jerusalem, Israel

    4 h-index

    7 publications

    464 citations

  5. University of California San Diego

    San Diego, United States

    4 h-index

    7 publications

    237 citations

  6. Princeton University

    Princeton, United States

    3 h-index

    7 publications

    1.3K citations

  7. University of Michigan

    Ann Arbor, United States

    3 h-index

    3 publications

    191 citations

  8. University of Washington

    Seattle, United States

    3 h-index

    4 publications

    138 citations

1–8 of 59

Venues

  1. SIAM Journal on Computing

    9 publications · 992 citations

    9

    h-index

  2. ArXiv.org

    Repository · 4 publications · 131 citations

    4

    h-index

  3. arXiv (Cornell University)

    Repository · 3 publications · 83 citations

    3

    h-index

  4. 2

    h-index

  5. Information and Computation

    2 publications · 61 citations

    2

    h-index

1–5