\( \def\<#1>{\left<#1\right>} \newcommand{\L}[1]{L_{\mathrm{bip}}(#1)} \newcommand{\disjpairs}{\mathcal{D}} \DeclareDocumentCommand\setdef{mo}{\left\{#1\IfNoValueTF{#2}{}{ : #2}\right\}} \)

Bipartite formula complexity: a progress towards Problem 6.57

A bipartite formula $F(x,y)$ has two groups of variables. Input leaves are arbitrary(!) boolean functions, each depending only on $x$-variables or on $y$-variables. Gates are AND and OR. For a boolean function $f(x,y)$ of $2n$ variables, let $\L{f}$ denote the minimum number of leaves in a bipartite formula computing $f$. [Note that $\L{f}$ is just the bipartite formula complexity of the bipartite $N\times N$ graph $G_f$ defined by $f$ with $N:=2^n$ (Sects. 1.7.1 and 6.15 in the book).]

It is clear that every (ordinary) DeMorgan formula is a very special bipartite formula with all input functions being trivial ones: variables or their negations. So, since the highest known lower bounds for DeMorgan formulas are only cubic in the number of variables, proving such a (cubic) lower bound for (more general) bipartite formulas is a hard task.

Using a recent upper bound of Reichardt on the degree of polynomials approximating formulas of a given size, Avishay Tal has shown that $\L{f}=\Omega(n^2/\log^2 n)$ holds for the inner product function $f=IP_n$. The graph $G_f$ of this function is the bipartite graph whose adjacency $\pm 1$ matrix is the $N\times N$ Hadamard $H$ matrix with $N=2^n$ (see Appendix A.3).

Recall the following theorem of Jürgen Forster (Sect. 4.11).

Theorem 1 (Forster [1]) The sign-rank of $H$ is at least $\sqrt{N}=2^{n/2}$.
The next main tool is the following result of Ben Reichardt. For the rest, it will be convenient to treat the boolean domain as $\{-1,1\}$. The transition between this domain and $\{0,1\}$ is given by simple functions $(1-x)/2$ and $(-1)^x$. Thus, $-1$ corresponds to $1$ ("true") and $+1$ to $0$ ("false").
Theorem 2 (Reichardt [2]) Suppose that a boolean function $f:\{-1,1\}^n\to\{-1,1\}$ can be computed by a DeMorgan formula of size $s$. Then there is a multilinear polynomial $p$ of degree $O(\sqrt{s})$ such that $|f(z)-p(z)|\leq 1/3$ holds for all $z\in\{-1,1\}^n$.
By the sign-rank of a boolean function $f:\{-1,1\}^{2n}\to\{-1,1\}$ we will mean the sign-rank of the matrix $M_f[x,y]=f(x,y)$.
Theorem 3 (Tal [3]) The sign-rank of any boolean function $f(x,y)$ is at most $s^{O(\sqrt{s})}$ where $s=\L{f}$.
Together with Theorem 1, this already yields the claimed lower bound $\L{f}=\Omega(n^2/\log^2 n)$ for the inner product function $f=IP_n$.

Proof (of Thm. 3): Take a bipartite formula $F(x,y)$ with $s$ leaves computing $f$. At the $i$-th leaf, a product $f_i(x)\cdot g_i(y)$ is computed, where one of $f_i,g_i$ is the constant 1). Let $F'$ be a read-once de Morgan formula obtained from $F$ by replacing the $i$-th input gate with a formal variable $z_i$, for all $i\in[s]$. Theorem 2 gives us a multilinear polynomial \[ p(z)=\sum_{S\subseteq [s]\colon |S|\leq d}c_S\prod_{i\in S}z_i \] of degree $d=O(\sqrt{s})$ such that $F'(z)-1/3\leq p(z)\leq F'(z)+1/3$ holds for all $z\in\{-1,1\}^s$. In particular, $\mathrm{sgn}(p(z))= F'(z)$ holds for all $z\in\{-1,1\}^s$. Now replace back input variables $z_i$ by the corresponding products $f_i(x)\cdot g_i(y)$. Then for every $x\in\{-1,1\}^n$ and $y\in\{-1,1\}^n$, the value $F(x,y)$ is the signum of \[ p(f_1(x)\cdot g_1(y),\cdots, f_1(x)\cdot g_1(y)) =\sum_{S\subseteq [s]\colon |S|\leq d}c_S\prod_{i\in S}f_i(x) \cdot \prod_{i\in S}g_i(y)\,. \] Each summand on the right-hand side corresponds to a matrix of rank $1$ over the reals. Hence, their sum corresponds to a matrix of rank at most the total number $s^{O(d)}=s^{O(\sqrt{s})}$ of summands. Thus, the matrix $M_f=f(x,y)$ of our function $f$ is at most $s^{O(\sqrt{s})}$, as claimed. $\Box$

References:

  1. J. Forster, A linear lower bound on the unbounded eror probabilistic communication complexity, J. Comput. Syst. Sci. 65:4 (2002) 612-625.
  2. B.W. Reichardt, Reflections for quantum query algorithms, arxiv.org/abs/1005.1601
  3. A. Tal, The bipartite formula complexity of Inner-Product is quadratic, ECCC Report No. 181, 2016.

S. Jukna, November 2016