Denote $P_{2n}$ to be collection of homogeneous total degree $2$ real polynomials in exactly $2n$ variables such that coefficient of every monomial is either $1$ or $-1$.
Split variable set into disjoint $S_r$, $S_c$ such that each of $S_r$, $S_c$ contains ${n}$ variables each.
Take an $f$ from $P_{2n}$.
Consider $n\times n$ matrix $M_f$ indexed by assigning row labels from variables in $S_r$, column labels from variables in $S_c$ with $(i,j)$ matrix entry given by evaluating polynomial on $\{0,1\}^{2n}$ such that only indices $i$ and $j$ of evaluation vector is $1$. Naturally $M_f$ is $\pm1$ valued.
What is good upper bound on $rank(M_f)$ if $\max_{\{0,1\}^{2n}}|f|=d$?
