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!  
SOS and the small set expansion property
cc.complexity theory;np hardness;semidefinite programming;sum of squares