• Firstly note this paper http://ttic.uchicago.edu/~madhurt/Papers/reductions.pdf where a Lasserre SDP is being setup for the independent set probblem at the bottom of page 4 where the author says says, "It can be shown that for any set S with |S| ≤ t, the vectors $U_{S'}$, S' ⊆ S induce a probability distribution over valid independent sets of the subgraph induced by S."

I guess that the author is claiming the following identity,for all subsets $S$ of size at most $t$, $\sum_{S' \subseteq S, S' \text{independent in the subgraph induced by }S} ||U_S'||_2^2 = 1$ Can someone clarify/prove that this above statement follows from whatever has been defined about these vectors $U_{S'}$ on page 4? (Is the author claiming that this equality above is a consequence of how he has defined the feasible set of $U_{S'}$ vectors in the top box of page $5$?)

  • I guess these vectors $U_{S'}$ can be interpreted as what I would call "Lasserre vectors" (is there any standard term for these?) (By ``Lassere vectors" I mean the rows of the matrix $V$ which factorizes the degree $d$ pseudo-moment matrix $M$ as $M = VV^T$) So is the author claiming that there is such a probabilistic interpretation for any Lassere vector?

  • For the Sherali-Adams SDP hierarchy let me follow the definition of $SA_r$ as in the box at the top of page $5$ here, http://dsteurer.org/paper/cspgaps.pdf. (...I haven't seen any book or other older paper define this notion! People seem to typically refer to a certain LP hierarchy as the Sherali-Adams hierarchy!...)

    Is there any relationship between this local integral distribution $\mu_S$ defined in this paper and the probability distribution alluded to in the first paper? Are the SDP vectors $v_{i,a}$ used in the $SA_R$ definition to be also thought of as or are even remotely related to Lasserre vectors?


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.