3
$\begingroup$

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

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

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.