A bipartite formula on binary variables $x_1, \ldots, x_n$ and $y_1, \ldots, y_n$ is a binary tree whose internal nodes are marked with AND or OR gates and whose leaves may compute any function of either the $x$ or $y$ variables. We show that any bipartite formula for the Inner-Product modulo 2 function, namely $IP(x,y) = \sum_{i=1}^{n} x_i y_i (mod~2)$, must be of size $\tilde{\Omega}(n^2)$. The result is tight up to logarithmic factors. To the best of our knowledge, this is the first super-linear lower bound on the bipartite formula complexity of any explicit function.

We give two simple proofs that rely on the deep results of Reichardt [SODA, 2011] and Forster [JCSS, 2002]. Moreover, the second proof establishes an average-case lower bound for the Inner-Product function. Namely, we show that any bipartite formula that agrees with $IP$ on at least $\frac{1}{2} + \frac{1}{n^{\log n}}$ of the inputs must be of size $\tilde{\Omega}(n^2)$.