Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR16-181 | 15th November 2016 22:28

The Bipartite Formula Complexity of Inner-Product is Quadratic


Authors: Avishay Tal
Publication: 15th November 2016 22:36
Downloads: 1832


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

ISSN 1433-8092 | Imprint