I'm trying to understand the paper The Bipartite Formula Complexity of Inner Product is Quadratic, by Avishay Tal. The argument is recapped here. I am having trouble understanding the proof Theorem 3 from that page.

The approach is to construct an polynomial approximation $p$ for the function $f$, and then show that the matrix $M_f$ is equal to the matrix consisting of sign$(p(x,y))$ for each entry $x,y$.

My question is regarding the following sentence, found on the very last paragraph of the page:

Each summand on the right-hand side corresponds to a matrix of rank 1 over the reals.

I do understand why this must be true. If I construct a matrix with coordinates corresponding to, say, the first summand evaluated at $x,y$ for each row/column $x,y$, I don't see why it must be rank-one.

  • 2
    $\begingroup$ Rank is 1, because every row is a scalar multiple of any fixed row. These scalars are determined by the values of the $f_i$s on the corresponding rows. The same holds also for columns: here scalars are determined by the values of the $g_i$s. $\endgroup$ – Stasys Jul 6 '19 at 17:06
  • $\begingroup$ You can now write $M=\sum_{S\subseteq[s]:|S|\leq d} c_S A_S B_S$, where $A_S \in \mathbb{R}^{N\times 1}$ and $B_S \in \mathbb{R}^{1\times N}$ are vectors defined as $A_S[x]=\prod_{i\in S} f_i(x), B_S[y]=\prod_{i\in S} g_i(y)$. From the dimension of $A_S$, $\textrm{rank}(A_S)\leq 1$, and, thus, $\textrm{rank}(c_S A_S B_S)\leq 1$. From sub-additivity of rank, the rank of the whole sum is now bounded from above by the total number of terms $s^{O(d)}$. $\endgroup$ – Alex Golovnev Jul 9 '19 at 18:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.