Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR20-155 | 22nd October 2020 19:10

Log-rank and lifting for AND-functions

RSS-Feed




Revision #1
Authors: Alexander Knop, Shachar Lovett, Sam McGuire, Weiqiang Yuan
Accepted on: 22nd October 2020 19:10
Downloads: 1346
Keywords: 


Abstract:

Let f: \{0,1\}^n \to \{0, 1\} be a boolean function, and let f_\land (x, y) = f(x \land y) denote the AND-function of f, where x \land y denotes bit-wise AND. We study the deterministic communication complexity of f_\land and show that, up to a \log n factor, it is bounded by a polynomial in the logarithm of the real rank of the communication matrix of f_\land. This comes within a \log n factor of establishing the log-rank conjecture for AND-functions with no assumptions on f. Our result stands in contrast with previous results on special cases of the log-rank
conjecture, which needed significant restrictions on f such as monotonicity or low \mathbb{F}_2-degree. Our techniques can also be used to prove (within a \log n factor) a lifting theorem for AND-functions, stating that the deterministic communication complexity of f_\land is polynomially-related to the AND-decision tree complexity of f.

The results rely on a new structural result regarding boolean functions f:\{0, 1\}^n \to \{0, 1\} with a sparse polynomial representation, which may be of independent interest. We show that if the polynomial computing f has few monomials then the set system of the monomials has a small hitting set, of size poly-logarithmic in its sparsity. We also establish extensions of this result to multi-linear polynomials f:\{0,1\}^n \to \mathbb{R} with a larger range.



Changes to previous version:

Fixed author order.


Paper:

TR20-155 | 18th October 2020 17:09

Log-rank and lifting for AND-functions





TR20-155
Authors: Alexander Knop, Shachar Lovett, Sam McGuire, Weiqiang Yuan
Publication: 18th October 2020 17:44
Downloads: 900
Keywords: 


Abstract:

Let f: \{0,1\}^n \to \{0, 1\} be a boolean function, and let f_\land (x, y) = f(x \land y) denote the AND-function of f, where x \land y denotes bit-wise AND. We study the deterministic communication complexity of f_\land and show that, up to a \log n factor, it is bounded by a polynomial in the logarithm of the real rank of the communication matrix of f_\land. This comes within a \log n factor of establishing the log-rank conjecture for AND-functions with no assumptions on f. Our result stands in contrast with previous results on special cases of the log-rank
conjecture, which needed significant restrictions on f such as monotonicity or low \mathbb{F}_2-degree. Our techniques can also be used to prove (within a \log n factor) a lifting theorem for AND-functions, stating that the deterministic communication complexity of f_\land is polynomially-related to the AND-decision tree complexity of f.

The results rely on a new structural result regarding boolean functions f:\{0, 1\}^n \to \{0, 1\} with a sparse polynomial representation, which may be of independent interest. We show that if the polynomial computing f has few monomials then the set system of the monomials has a small hitting set, of size poly-logarithmic in its sparsity. We also establish extensions of this result to multi-linear polynomials f:\{0,1\}^n \to \mathbb{R} with a larger range.



ISSN 1433-8092 | Imprint