Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR16-181 | 15th November 2016 22:28

#### The Bipartite Formula Complexity of Inner-Product is Quadratic

TR16-181
Authors: Avishay Tal
Publication: 15th November 2016 22:36
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)$.