Communication complexity of permutation-invariant functions

DOI10.1137/1.9781611974331.CH134MaRDI QIDQ4575718zbMATH OpenOpenAlexFDO

Authors Badih Ghazi, Pritish Kamath, Madhu Sudan

Publication date 16 July 2018

Published in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1506.00273

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: Motivated by the quest for a broader understanding of communication complexity of simple functions, we introduce the class of "permutation-invariant" functions. A partial function $f:{0,1}^{n}imes{0,1}^{n}o0,1,?$ is permutation-invariant if for every bijection $pi:1,ldots,no1,ldots,n$ and every $mathbfx,mathbfyin{0,1}^n$, it is the case that $f(mathbfx,mathbfy)=f(mathbf{x}^{pi},mathbf{y}^{pi})$. Most of the commonly studied functions in communication complexity are permutation-invariant. For such functions, we present a simple complexity measure (computable in time polynomial in $n$ given an implicit description of $f$) that describes their communication complexity up to polynomial factors and up to an additive error that is logarithmic in the input size. This gives a coarse taxonomy of the communication complexity of simple functions. Our work highlights the role of the well-known lower bounds of functions such as 'Set-Disjointness' and 'Indexing', while complementing them with the relatively lesser-known upper bounds for 'Gap-Inner-Product' (from the sketching literature) and 'Sparse-Gap-Inner-Product' (from the recent work of Canonne et al. [ITCS 2015]). We also present consequences to the study of communication complexity with imperfectly shared randomness where we show that for total permutation-invariant functions, imperfectly shared randomness results in only a polynomial blow-up in communication complexity after an additive $O(loglogn)$ overhead.

Recommendations

• Communication with imperfectly shared randomness
• Communication complexities of symmetric XOR functions
• Communication complexity of two decision problems
• Harmonic analysis, real approximation, and the communication complexity of Boolean functions
• Composition theorems in communication complexity

Cited in

(5)

• Functional inversion and communication complexity
• The communication complexity of interleaved group products
• scientific article; zbMATH DE number 88975 (Why is no real title available?)
• Dimension Reduction for Polynomials over Gaussian Space and Applications
• Quantum and classical communication complexity of permutation-invariant functions

This page was built for publication: Communication complexity of permutation-invariant functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575718)