2
$\begingroup$
  • 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?

$\endgroup$

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.