<p>I'm trying to understand the paper <em>The Bipartite Formula Complexity of Inner Product is Quadratic</em>, by Avishay Tal. The argument is recapped <a href="http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/comment20.html" rel="nofollow noreferrer">here</a>. I am having trouble understanding the proof Theorem 3 from that page.</p>

<p>The approach is to construct an polynomial approximation <span class="math-container">$p$</span> for the function <span class="math-container">$f$</span>, and then show that the matrix <span class="math-container">$M_f$</span> is equal to the matrix consisting of sign<span class="math-container">$(p(x,y))$</span> for each entry <span class="math-container">$x,y$</span>.</p>

<p><strong>My question is</strong> regarding the following sentence, found on the very last paragraph of the page:</p>

<blockquote>
  <p>Each summand on the right-hand side corresponds to a matrix of rank 1 over the reals.</p>
</blockquote>

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

CC BY-SA 4.0
2019-07-06T17:06:50.887Z
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.
Stasys
CC BY-SA 4.0
2019-07-09T18:31:04.663Z
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)}$.
Alex Golovnev
<cc.complexity-theory><communication-complexity><query-complexity><boolean-formulas>
Bipartite formula complexity lower bound
NNN
# Bipartite formula complexity lower bound

(Asked by: username_0 on 2019-07-05)

I'm trying to understand the paper *The Bipartite Formula Complexity of Inner Product is Quadratic*, by Avishay Tal. The argument is recapped [here](http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/comment20.html). 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.

**Tags:** cc.complexity-theory, communication-complexity, query-complexity, boolean-formulas
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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)}$.  

---

## 0 answers

