On the Communication Complexity of AND Functions
Author:
- 19 January 2021
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 67 (7) , 4929-4935
Abstract
Log-rank conjecture is one of challenging problems in communication complexity. It is known to hold for some special function classes such as XOR functions $\text {f}(\text {x}\oplus \text {y})$ when the outer function f is monotone, symmetric, $\mathsf {AC}^{0}$ , low $\mathbb {F}_{2}$ -degree, linear threshold or read-k. However, for AND functions $\text {f}(\text {x}\wedge \text {y})$ , Log-rank conjecture is only known to hold when the outer function is a monotone function or a function with small alternating numbers. In this paper, we show that Log-rank conjecture holds for AND functions whose outer functions are read-once $\mathbb {F}_{2}$ -degree polynomials, constant- $\mathbb {F}_{2}$ -degree polynomials, and symmetric functions. For read-once and symmetric AND functions, their proof are based on the elementary analysis of Möbius sparsity of the outer functions and designing efficient protocols for computing the corresponding AND functions in terms of the Möbius sparsity of their outer functions. For a constant- $\mathbb {F}_{2}$ -degree AND function $\text {f}(\text {x}\wedge \text {y})$ , we use the concept of the variable rank to design a decision tree for computing f where the tree depth is bounded above by a polynomial in the logarithm of the Möbius sparsity of f. The communication protocol can be obtained easily from the constructed decision tree. Our results deepen the understanding of the log-rank conjecture for AND functions.Keywords
Funding Information
- Ministry of Science and Technology of Taiwan (MOST-109-2221-E-305-005)
This publication has 11 references indexed in Scilit:
- Communication is Bounded by Root of RankJournal of the ACM, 2016
- On the Structure of Boolean Functions with Small Spectral Normcomputational complexity, 2015
- Efficient quantum protocols for XOR functions2013
- Fourier Sparsity, Spectral Norm, and the Log-Rank Conjecture2013
- Query Complexity of Matroids2013
- On the parity complexity measures of Boolean functionsTheoretical Computer Science, 2010
- On the structure of cubic and quartic polynomials2010
- The polynomial method in circuit complexity2002
- Complexity measures and decision tree complexity: a surveyTheoretical Computer Science, 2002
- Lattices, mobius functions and communications complexity1988