I am kind of confused by the argument at the top of page 5 here, http://homes.cs.washington.edu/~jrl/notes/bonn-lecture-notes.pdf

  • Firstly given that the author wanted to look at quadratic multilinear functions on $\{0,1\}^n$ why is he finding it enough to look at functions of the form, $f(x) = a_0 + \sum_{i,j} A_{ij}(xx^T)_{ij}$ for some real symmetric matrix $A$ and a real number $a_0$?

    These $f$s won't have any linear term and doesn't that mean a loss of generality?

  • The author defines the set $QML_n^+$ as the set of functions of the above type which are non-negative on the Boolean hypercube. Isn't this set an uncountably infinite set?

    Because I don't understand how the author now hopes to define a matrix $M_n$ whose rows seem indexes by $f \in QML_n^+$ and the columns seem indexed by $x \in \{0,1\}^n$ and the entries are $M_n(f,x) = f(x)$.

    How does this make sense as a matrix (of finite dimensions!)?

  • Given everything above how is it obvious that this matrix $M_n$ is a submatrix of some slack matrix of the correlation polytope $conv(\{ xx^T \vert x \in\{0,1\}^n \})$ ?

  • $\begingroup$ It's usually best to limit yourself to one question per post. This site doesn't work as well for questions with multiple questions: if someone answers one of them but not others, the question gets marked as answered. I recommend you start by asking a single question -- usually, the first question you run across. If you're lucky, the answer to that question might then help you work out the answer to the others. If not, you can always ask a second question. $\endgroup$ – D.W. Mar 9 '16 at 4:54

Every quadratic multilinear polynomial can be written as $$ a_0 + \sum_i a_{ii} x_i + \sum_{i \neq j} a_{ij} x_i x_j = a_0 + \sum_i a_{ii} x_i^2 + \sum_{i \neq j} a_{ij} x_i x_j, $$ using the fact that $x_i^2 = x_i$ for every $x_i \in \{0,1\}$. This clearly equals $a_0 + \sum_{ij} A_{ij} x_i x_j$, which in turn is the same as what you wrote.

Regarding the matrix $M_n$, it is indeed infinite. For the proof that it is a submatrix of some slack matrix of the correlation polytope, see Lemma 2.8 of these lecture notes by James Lee.

If you have any more questions on the Bonn lecture notes, I suggest looking in the cited lecture notes, which seem to be more thorough.

  • $\begingroup$ Thanks! It wasn't clear to me if the equality was claimed in general! So it seems that its equal only on the hypercube. $\endgroup$ – gradstudent Mar 9 '16 at 15:33

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.