ECCC-Report TR20-155https://eccc.weizmann.ac.il/report/2020/155Comments and Revisions published for TR20-155en-usThu, 22 Oct 2020 19:10:22 +0300
Revision 1
| Log-rank and lifting for AND-functions |
Sam McGuire,
Shachar Lovett,
Alexander Knop,
Weiqiang Yuan
https://eccc.weizmann.ac.il/report/2020/155#revision1Let $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.
Thu, 22 Oct 2020 19:10:22 +0300https://eccc.weizmann.ac.il/report/2020/155#revision1
Paper TR20-155
| Log-rank and lifting for AND-functions |
Sam McGuire,
Shachar Lovett,
Alexander Knop,
Weiqiang Yuan
https://eccc.weizmann.ac.il/report/2020/155Let $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.
Sun, 18 Oct 2020 17:44:03 +0300https://eccc.weizmann.ac.il/report/2020/155