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$?

  • $\begingroup$ Your notation is unclear. What is $|f|$? $\endgroup$ – kodlu Sep 10 '15 at 22:21
  • $\begingroup$ Maximum absolute value over all points on the cube $\endgroup$ – Brout Sep 10 '15 at 22:42

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.