For what graphs do we know that their small set expansion property has a low degree SOS proof? Is this known to be true for say the complete graphs?

A terminology issue about what is ``low degree" :

Around page 13 here, http://www.boazbarak.org/sos/files/lec2d.pdf, when this was shown for the Boolean hypercube graph the author claimed that this is a degree $4$ SOS certificate. This terminology is a bit peculiar to me. Because as one sees in the proof it uses non-negativity of the pseudo-expectation of polynomials of the form $(fg)^2$ where $f$ and $g$ are degree at most $d$ polynomials in $n-1$ variables. So I think this should have been called a degree $4d$ SOS certificate. But somehow they want to see this as a degree $4$ SOS proof in the space of Fourier coeffients because the product $fg$ is obviously degree $2$ over Fourier coefficients. I am not sure if this way of thinking makes sense! It would be helpful to know why this way of counting makes sense!

  • $\begingroup$ Regarding your terminology issue: did you read the discussion after Lemma 10? It states explicitly that "These [$L_x(f)^4$] are polynomials in the coefficients of $f$." I.e., for $x$ fixed, $L_{x}\colon (f_\alpha)_\alpha$ is a function which takes the set of coefficients of a polynomial $f$ and returns $L_x(f)=f(x)$ (so $L_x$ is a linear function). Why don't you think this makes sense? $\endgroup$ – Clement C. Jan 28 '17 at 3:06
  • $\begingroup$ Well, that comment is what I find to be a puzzling way to count. The statement of Lemma $10$ is not a fixed $x$ statement. It is taking a pseudo-expectation over some pseudo-distribution over the hypercube. Then isn't it obvious and natural that the quantity of which one is taking the pseudo-expectation be considered a function of $x$ and in that case the degree of the polynomial whose pseudo-expectation one is invoking to be non-negative is of degree $4d$ in $x$. $\endgroup$ – gradstudent Jan 28 '17 at 3:28
  • $\begingroup$ Whenever you say something is low degree you need to know what the variables are. Here the variables are the coefficients of $f$. The $\mathbb{E}_x$ symbols in the lemma denote actual expectation, not pseudoexpectation. After the lemma, it is mentioned that it implies you can take pesudoexpectation over $f$. $\endgroup$ – Sasho Nikolov Jan 28 '17 at 15:03
  • 1
    $\begingroup$ It may help to keep Lemma 10 in context. The idea is to prove that the boolean hypercube is a small-set expander, and their argument involves looking at eigenspaces of that graph. The natural variables then are the entries in vectors indexed by $\{\pm 1\}^n$. Their proof takes the conceptual point of view that these vectors are functions $\{\pm 1\}^n \to \mathbb{R}$ (whose degree $d$ is relevant). Consequently the natural variables in the SOS proof are the values of these functions. $\endgroup$ – Andrew Morgan Jan 28 '17 at 16:31

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.