<p>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? </p>

<hr>

<p>A terminology issue about what is ``low degree" : </p>

<p>Around page 13 here, <a href="http://www.boazbarak.org/sos/files/lec2d.pdf" rel="nofollow noreferrer">http://www.boazbarak.org/sos/files/lec2d.pdf</a>, 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!  </p>

CC BY-SA 3.0
2017-01-28T03:06:01.810Z
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?
Clement C.
CC BY-SA 3.0
2017-01-28T03:28:35.537Z
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$.
gradstudent
CC BY-SA 3.0
2017-01-28T15:03:21.190Z
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$.
Sasho Nikolov
CC BY-SA 3.0
2017-01-28T16:31:24.613Z
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.
Andrew Morgan
<cc.complexity-theory><np-hardness><semidefinite-programming><sum-of-squares>
SOS and the small set expansion property
gradstudent
# SOS and the small set expansion property

(Asked by: username_0 on 2017-01-27)

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!

**Tags:** cc.complexity-theory, np-hardness, semidefinite-programming, sum-of-squares
> **Comments:**
> **username_1**: 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?  
> **username_0**: 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$.  
> **username_2**: 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$.  
> **username_3**: 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.  

---

## 0 answers

