ECCC-Report TR16-181https://eccc.weizmann.ac.il/report/2016/181Comments and Revisions published for TR16-181en-usTue, 15 Nov 2016 22:36:13 +0200
Paper TR16-181
| The Bipartite Formula Complexity of Inner-Product is Quadratic |
Avishay Tal
https://eccc.weizmann.ac.il/report/2016/181A 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)$. Tue, 15 Nov 2016 22:36:13 +0200https://eccc.weizmann.ac.il/report/2016/181