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!