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).

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 1(Forster [1]) The sign-rank of $H$ is at least $\sqrt{N}=2^{n/2}$.

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 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$.

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$.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}$.

** 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$

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

S. Jukna, November 2016