Inner Product and Set Disjointness
| Autor: | Alexander A. Sherstov, Vladimir V. Podolskii |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
FOS: Computer and information sciences
Discrete mathematics 020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology Computational Complexity (cs.CC) Binary logarithm 01 natural sciences Theoretical Computer Science Set (abstract data type) Computer Science - Computational Complexity Computational Theory and Mathematics 010201 computation theory & mathematics Product (mathematics) 0202 electrical engineering electronic engineering information engineering Communication complexity Mathematics |
| Zdroj: | ACM Transactions on Computation Theory. 12:1-28 |
| ISSN: | 1942-3462 1942-3454 |
| DOI: | 10.1145/3428671 |
| Popis: | A major goal in complexity theory is to understand the communication complexity of number-on-the-forehead problems f :({0, 1} n ) k → {0, 1} with k > log n parties. We study the problems of inner product and set disjointness and determine their randomized communication complexity for every k ≥ log n , showing in both cases that Θ(1 + ⌈log n ⌉/ log ⌈1 + k / log n ⌉) bits are necessary and sufficient. In particular, these problems admit constant-cost protocols if and only if the number of parties is k ≥ n ϵ for some constant ϵ > 0. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|