Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR16-181 | 15th November 2016 22:28

The Bipartite Formula Complexity of Inner-Product is Quadratic

RSS-Feed




TR16-181
Authors: Avishay Tal
Publication: 15th November 2016 22:36
Downloads: 1963
Keywords: 


Abstract:

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