<p>Yes, that's exactly what it is: optimizing over higher degree pseudoexpectations. The results I think you refer to prove that the hypercontractive inequality holds when $f$ is replaced by a degree $4$ pseudo distribution over $\mathbb{R}^{\{-1,1\}^n}$, which is stronger than the classical theorem (see Lemma 2.10 in Boaz's notes). Specifically, the stronger Lasserre version of the inequality is that for any degree 4 pseudo expectation operator $\tilde{\mathbb{E}}$ over $f:\{-1,1\}^n\to \mathbb{R}$ we have</p>

<p>$$
\tilde{\mathbb{E}} [\|\Pi_d f\|_4^4] \leq 9^d \tilde{\mathbb{E}}[\|\Pi_d f\|_2^4],
$$
where $\Pi_d$ is the linear projection operator onto the span of degree $d$ polynomials on $\{-1, 1\}^n$, and for $g:\{-1, 1\}^n\to \mathbb{R}$, the $L^p$ norm is defined as 
$$
\|g\|_p = (\mathbb{E}_{x} g(x)^p)^{1/p} = \left(\frac{1}{2^n}\sum_{x \in \{-1, 1\}^n} g(x)^p\right)^{1/p}.
$$</p>

<p>Equivalently, this means that the inequality can be proved in a weak proof system, the degree $4$ sum of squares proof system, which is the statement given in Lemma 2.10 in Boaz's notes. See the discussion after the statement of the lemma.</p>

<p>(Something that may be confusing is that there are two different classes of polynomials going on here. One is the degree $d$ polynomials on $\{-1, 1\}^n$: you should treat these as just a subspace of $\mathbb{R}^{\{-1,1\}^n}$. The other class of polynomials are the polynomials that arise in the sum of squares proof of the hypercontractive inequality. These are polynomials <em>over the values of $f$</em>.)</p>

<p>The reason this is interesting is that it gives a low degree sum of squares proof that the hypercube graph is a small set expander. Roughly speaking, the fact that the cube is a small set expander is one of the main ingredients of proving that certain instances of the unique games problem are "hard" for some weaker SDPs, for example for constant number of rounds of the Sherali Adams + SDP hierarchy (SA+SDP). I.e. on these instances SA+SDP overestimates how many constraints can be satisfied, and in some sense the reason is that it "does not know" that the hypercube is  a small set expander. (This is only a rough intuition, the hard instances for Sherali Adams are much more complicated than the hypercube.)</p>

<p>By contrast, because there is a low degree sum of squares proof that the hypergraph is a small set expander (again, I am oversimplifying a lot here, and there are many more ingredients you need), these same instances <em>are not</em> hard even for 8 rounds of Lasserre, i.e. the Lasserre SDP <em>does not</em> overestimate how many constraints can be satisfied in these instances. The precise statement of this result is Theorem 6.1. in the paper <a href="http://arxiv.org/abs/1205.4484v3" rel="nofollow">Hypercontractivity, Sum-of-Squares Proofs, and their Applications</a>. This is interesting, because these were our best candidates for hard instances of unique games. Essentially, we do not know any distribution on unique games instances (or instances of the small set expansion problem) which are not solved with high probability by constant round Lasserre. You may take this as some evidence that unique games may not be hard after all.</p>

CC BY-SA 3.0
2015-03-31T19:13:43.533Z
Thanks for the reply! (1) Can you give a reference to this result you quote that the hypercontractive inequality holds for $O(d)$ pseudoexpectations? (I guess what you call "d" is the same $d$ as it occurs in my post) (b) Can't this hypercontractivity be shown for arbitrarily large degree pseudoexpectations?
Student
CC BY-SA 3.0
2015-03-31T19:17:06.387Z
(c) I know the proof that the hypercube graph is a small-set expander and that proof follows directly from this "2-4" hypercontractive inequality that I quoted. But how does that proof show that the hypercube is not a hard-instance for 8 rounds of Lasserre? I am not seeing how this conclusion follows from the proof...(how do you frame this as a "distribution on unique games instances"?)
Student
CC BY-SA 3.0
2015-03-31T19:23:18.240Z
(d) Most specifically, what we can show for the hypercube is that, for any eigenvalue $\lambda \in (0,1)$ of $L = I - \frac{A}{d}$, for all $S \subseteq V$ s.t $\mu(S) \leq \delta$ we have $\phi(S) \geq \lambda(1-\sqrt{C \delta} )$ - And isn't showing this the same as disproving the SSEH on the hypercube?
Student
CC BY-SA 3.0
2015-03-31T19:33:15.247Z
where $C$ above is the 2-4 hypercontractive norm bound - which happens to be $9^{\lambda n}$ for the n-hypercube.
Student
CC BY-SA 3.0
2015-03-31T20:11:40.903Z
The reference is Lemma 2.10 in the notes, or Lemma 5.1. in the paper "Hypercontractivity, sum-of-squares proofs, and their applications". The "hard" instances that turn out not to be hard for Lasserre are not exactly the cube, see Theorems 2.6 and 6.1. in the latter paper. The SoS proof of the hypercontractive inequality is only one ingredient in proving that they are not hard for Lasserre, but an important one. See Section 6 of the same paper for the details.
Sasho Nikolov
CC BY-SA 3.0
2015-03-31T20:24:33.043Z
I know that lemma 5.1 in that paper - its still a 2-4 result and with ordinary expectations (the same as I quoted in the post) - I thought you meant a higher hypercontractivity result with maybe pseudo-expectations - right?
Student
CC BY-SA 3.0
2015-03-31T21:15:46.657Z
I am sorry, I might've caused some of the confusion. In fact the degree you need is just 4. The expectation in the usual statement of the inequality is not the issue: this is just normalization for the $L^p$ norms. The point is that $f$ can be replaced by a pseudo distribution: see my edit. The main thing in Lemma 5.1 is that the inequality sign is replaced by $\preceq$, i.e. the difference between the right and left hand side is a sum of squared polynomials. This is equivalent to the pseudo distribution formulation.
Sasho Nikolov
CC BY-SA 3.0
2015-03-31T23:05:54.657Z
This is very confusing - the inequality you state in the post is neither Lemma 5.1 of that paper you refer to nor is it Lemma 2.10 of Barak's notes - is there anyway to see how these are related?
user6818
CC BY-SA 3.0
2015-03-31T23:29:33.150Z
@SashoNikolov Thanks! So this 2-4 hypercontractivity inequality as I stated it in the post does go into disproving the SSEH on the Boolean cube - right?
Student
CC BY-SA 3.0
2015-04-01T01:07:41.270Z
"SSEH on the Boolean cube" doesn't make sense to me. If you are going to conjecture that a decision problem is hard on a class of instances, that class better contain both yes and no instances. The inequality I wrote is equivalent to Lemma 2.10 in the notes, because sum of squares proofs are dual to the Lasserre hierarchy. See the paragraph after Lemma 2.10: Boaz states essentially the same inequality I stated, but with different notation, and I think he omitted the projection operator, which may be a typo.
Sasho Nikolov
CC BY-SA 3.0
2015-04-01T01:36:59.440Z
@SashoNikolov (Thats what my last bullet point was) The 2-4 hypercontractivity theorem is exactly the same as saying that for any normalized Laplacian eigenvalue of the Boolean n-hypercube, the subpspace of eigenvectors with that or lower eigenvalues is 2-4 hypercontractive. Hence the theorem 2.8 of Barak's notes will apply on it and we have a guarantee on the expansion of all subsets of the hypercube. Hence we have shown that the n-Boolean hypercube is a small-set expander. Isn't this equivalent to giving an affirmative answer to the SSEH for the Boolean n-hypercube instance?
Student
CC BY-SA 3.0
2015-04-01T01:38:41.493Z
This is what I would guess be said as "giving a degree-4 SOS certificate" for the Boolean n-hypercube being a small-set expander. And this is supposed to be surprising since the Boolean n-hypercube is a hard-case of UGC?
Student
CC BY-SA 3.0
2015-04-02T19:14:40.263Z
@SashoNikolov I am not getting what is wrong about the phrase ``SSEH on the hypercube". SSEH is a statement of the form "Given a regular graph xyz decision question is hard" - So why doesn't it make sense to say that theorem 2.8 and Lemma 2.10 of Barak's notes imply that "On the Boolean hypercube the xyz decision question is easy" - which is what I would mean by saying that "SSEH on the Boolean hypercube is easy" - what is wrong here?
Student
CC BY-SA 3.0
2015-04-02T21:35:53.083Z
There is only one instance of the hypercube graph for each power of 2. Such sparse problems are always unlikely to be hard. Moreover, since each such instance is a small set expander, the trivial algorithm that always outputs yes solves the problem on the hypercube. So sure, the problem is easy on the hypercube, but it's weird to consider a problem only on a very sparse set of yes-only instances. And you don't need SoS to show that it's easy. It **is** interesting that the hypercube is easy for SoS, but the reason is that this is an **ingredient** in solving a much bigger set of instances.
Sasho Nikolov
CC BY-SA 3.0
2015-04-02T23:34:56.497Z
Thanks! What is the much bigger/non-sparse set of instances for which a similar degree-4 SOS certificate for the small-set expansion hypothesis exists? (for which apparently the proof on the hypercube is an ingredient!)
Student
CC BY-SA 3.0
2015-04-03T00:20:58.807Z
The ones in Theorem 6.1. in http://arxiv.org/pdf/1205.4484v3.pdf
Sasho Nikolov
CC BY-SA 3.0
2015-04-03T06:13:26.180Z
Is this the same as the claim that the UGC on the "noisy cube" has an efficient deg-4 SOS certificate? Or is that something else?
Student
CC BY-SA 3.0
2015-03-31T18:39:21.330Z
2015-03-31T21:25:54.043Z
2015-03-31T21:25:54.043Z
Sasho Nikolov
<ul>
<li>Is that the same as saying the one will try to generate a higher-degree "pseudo expectation functional" by solving a SOS-program ? Or is there a difference between the two things? </li>
</ul>

<hr>

<p>Or to take a different view, </p>

<hr>

<p>We needed to show that the projector to low-degree polynomials has bounded hypercontractive norm. We start off defining the projector $\mathcal{P}_d$ as the map,
$$\mathcal{P}_d : ( \{ \pm \}^n \rightarrow \mathbb{R}   )  \rightarrow  ( \{ \pm \}^n \rightarrow \mathbb{R}  )$$
$$ f = \sum_{\alpha \subseteq [n] }\hat {f}_\alpha \chi_\alpha  \rightarrow f' = \sum_{\vert \alpha\vert \leq d } \hat{f}_\alpha \chi_\alpha$$</p>

<p>Where $\chi_\alpha = \prod_{i \in \alpha} x_i$</p>

<p>Then we show that the over the space of such ''$n-$variate Fourier polynomials" $f'$ with degree at most $d$, $\mathbb{E} [f'^4 ] \leq 9^d ( \mathbb{E} [ f'^2 ] )^2  $ (which is equivalent to showing that  $\Vert \cal{P} \Vert_{2 \rightarrow 4 } \leq 9^d$ ) </p>

<ul>
<li><p>So in the above context is the choice of ``4" what quantifies the number of "rounds" of Lasserre hierarchy used? (the above is called a degree-4 SOS proof!) (as in you can run the SOS-program trying to optimize the hypercontractive norm of an operator only for as large a value of $x$(here $4$) as for which above kind of hypercontractive bounds can be established?) </p></li>
<li><p>Since this hypercontractive bound on such projection operators is already proven as a theorem then what does the so-called "Tensor-SDP" algorithm achieve in terms of giving an "efficient certificate"?</p></li>
</ul>

<cc.complexity-theory><approximation-algorithms><approximation-hardness><unique-games-conjecture>
What are multiple rounds of SOS/Lasserre hierarchy?
Student
# What are multiple rounds of SOS/Lasserre hierarchy?

(Asked by: username_0 on 2015-03-31)

* Is that the same as saying the one will try to generate a higher-degree "pseudo expectation functional" by solving a SOS-program ? Or is there a difference between the two things?

---

Or to take a different view,

---

We needed to show that the projector to low-degree polynomials has bounded hypercontractive norm. We start off defining the projector $\mathcal{P}\_d$ as the map,
$$\mathcal{P}\_d : ( \{ \pm \}^n \rightarrow \mathbb{R} ) \rightarrow ( \{ \pm \}^n \rightarrow \mathbb{R} )$$
$$ f = \sum\_{\alpha \subseteq [n] }\hat {f}\_\alpha \chi\_\alpha \rightarrow f' = \sum\_{\vert \alpha\vert \leq d } \hat{f}\_\alpha \chi\_\alpha$$

Where $\chi\_\alpha = \prod\_{i \in \alpha} x\_i$

Then we show that the over the space of such ''$n-$variate Fourier polynomials" $f'$ with degree at most $d$, $\mathbb{E} [f'^4 ] \leq 9^d ( \mathbb{E} [ f'^2 ] )^2 $ (which is equivalent to showing that $\Vert \cal{P} \Vert\_{2 \rightarrow 4 } \leq 9^d$ )

* So in the above context is the choice of ``4" what quantifies the number of "rounds" of Lasserre hierarchy used? (the above is called a degree-4 SOS proof!) (as in you can run the SOS-program trying to optimize the hypercontractive norm of an operator only for as large a value of $x$(here $4$) as for which above kind of hypercontractive bounds can be established?)
* Since this hypercontractive bound on such projection operators is already proven as a theorem then what does the so-called "Tensor-SDP" algorithm achieve in terms of giving an "efficient certificate"?

**Tags:** cc.complexity-theory, approximation-algorithms, approximation-hardness, unique-games-conjecture


---

## 1 answers

### Answer by username_1 on 2015-03-31. Score: 2

Yes, that's exactly what it is: optimizing over higher degree pseudoexpectations. The results I think you refer to prove that the hypercontractive inequality holds when $f$ is replaced by a degree $4$ pseudo distribution over $\mathbb{R}^{\{-1,1\}^n}$, which is stronger than the classical theorem (see Lemma 2.10 in Boaz's notes). Specifically, the stronger Lasserre version of the inequality is that for any degree 4 pseudo expectation operator $\tilde{\mathbb{E}}$ over $f:\{-1,1\}^n\to \mathbb{R}$ we have

$$
\tilde{\mathbb{E}} [\|\Pi\_d f\|\_4^4] \leq 9^d \tilde{\mathbb{E}}[\|\Pi\_d f\|\_2^4],
$$
where $\Pi\_d$ is the linear projection operator onto the span of degree $d$ polynomials on $\{-1, 1\}^n$, and for $g:\{-1, 1\}^n\to \mathbb{R}$, the $L^p$ norm is defined as
$$
\|g\|\_p = (\mathbb{E}\_{x} g(x)^p)^{1/p} = \left(\frac{1}{2^n}\sum\_{x \in \{-1, 1\}^n} g(x)^p\right)^{1/p}.
$$

Equivalently, this means that the inequality can be proved in a weak proof system, the degree $4$ sum of squares proof system, which is the statement given in Lemma 2.10 in Boaz's notes. See the discussion after the statement of the lemma.

(Something that may be confusing is that there are two different classes of polynomials going on here. One is the degree $d$ polynomials on $\{-1, 1\}^n$: you should treat these as just a subspace of $\mathbb{R}^{\{-1,1\}^n}$. The other class of polynomials are the polynomials that arise in the sum of squares proof of the hypercontractive inequality. These are polynomials *over the values of $f$*.)

The reason this is interesting is that it gives a low degree sum of squares proof that the hypercube graph is a small set expander. Roughly speaking, the fact that the cube is a small set expander is one of the main ingredients of proving that certain instances of the unique games problem are "hard" for some weaker SDPs, for example for constant number of rounds of the Sherali Adams + SDP hierarchy (SA+SDP). I.e. on these instances SA+SDP overestimates how many constraints can be satisfied, and in some sense the reason is that it "does not know" that the hypercube is a small set expander. (This is only a rough intuition, the hard instances for Sherali Adams are much more complicated than the hypercube.)

By contrast, because there is a low degree sum of squares proof that the hypergraph is a small set expander (again, I am oversimplifying a lot here, and there are many more ingredients you need), these same instances *are not* hard even for 8 rounds of Lasserre, i.e. the Lasserre SDP *does not* overestimate how many constraints can be satisfied in these instances. The precise statement of this result is Theorem 6.1. in the paper [Hypercontractivity, Sum-of-Squares Proofs, and their Applications](http://arxiv.org/abs/1205.4484v3). This is interesting, because these were our best candidates for hard instances of unique games. Essentially, we do not know any distribution on unique games instances (or instances of the small set expansion problem) which are not solved with high probability by constant round Lasserre. You may take this as some evidence that unique games may not be hard after all.

> **Comments:**
> **username_0**: Thanks for the reply! (1) Can you give a reference to this result you quote that the hypercontractive inequality holds for $O(d)$ pseudoexpectations? (I guess what you call "d" is the same $d$ as it occurs in my post) (b) Can't this hypercontractivity be shown for arbitrarily large degree pseudoexpectations?  
> **username_0**: (c) I know the proof that the hypercube graph is a small-set expander and that proof follows directly from this "2-4" hypercontractive inequality that I quoted. But how does that proof show that the hypercube is not a hard-instance for 8 rounds of Lasserre? I am not seeing how this conclusion follows from the proof...(how do you frame this as a "distribution on unique games instances"?)  
> **username_0**: (d) Most specifically, what we can show for the hypercube is that, for any eigenvalue $\lambda \in (0,1)$ of $L = I - \frac{A}{d}$, for all $S \subseteq V$ s.t $\mu(S) \leq \delta$ we have $\phi(S) \geq \lambda(1-\sqrt{C \delta} )$ - And isn't showing this the same as disproving the SSEH on the hypercube?  
> **username_0**: where $C$ above is the 2-4 hypercontractive norm bound - which happens to be $9^{\lambda n}$ for the n-hypercube.  
> **username_1**: The reference is Lemma 2.10 in the notes, or Lemma 5.1. in the paper "Hypercontractivity, sum-of-squares proofs, and their applications". The "hard" instances that turn out not to be hard for Lasserre are not exactly the cube, see Theorems 2.6 and 6.1. in the latter paper. The SoS proof of the hypercontractive inequality is only one ingredient in proving that they are not hard for Lasserre, but an important one. See Section 6 of the same paper for the details.  
> **username_0**: I know that lemma 5.1 in that paper - its still a 2-4 result and with ordinary expectations (the same as I quoted in the post) - I thought you meant a higher hypercontractivity result with maybe pseudo-expectations - right?  
> **username_1**: I am sorry, I might've caused some of the confusion. In fact the degree you need is just 4. The expectation in the usual statement of the inequality is not the issue: this is just normalization for the $L^p$ norms. The point is that $f$ can be replaced by a pseudo distribution: see my edit. The main thing in Lemma 5.1 is that the inequality sign is replaced by $\preceq$, i.e. the difference between the right and left hand side is a sum of squared polynomials. This is equivalent to the pseudo distribution formulation.  
> **username_2**: This is very confusing - the inequality you state in the post is neither Lemma 5.1 of that paper you refer to nor is it Lemma 2.10 of Barak's notes - is there anyway to see how these are related?  
> **username_0**: @SashoNikolov Thanks! So this 2-4 hypercontractivity inequality as I stated it in the post does go into disproving the SSEH on the Boolean cube - right?  
> **username_1**: "SSEH on the Boolean cube" doesn't make sense to me. If you are going to conjecture that a decision problem is hard on a class of instances, that class better contain both yes and no instances. The inequality I wrote is equivalent to Lemma 2.10 in the notes, because sum of squares proofs are dual to the Lasserre hierarchy. See the paragraph after Lemma 2.10: Boaz states essentially the same inequality I stated, but with different notation, and I think he omitted the projection operator, which may be a typo.  
> **username_0**: @SashoNikolov (Thats what my last bullet point was) The 2-4 hypercontractivity theorem is exactly the same as saying that for any normalized Laplacian eigenvalue of the Boolean n-hypercube, the subpspace of eigenvectors with that or lower eigenvalues is 2-4 hypercontractive. Hence the theorem 2.8 of Barak's notes will apply on it and we have a guarantee on the expansion of all subsets of the hypercube. Hence we have shown that the n-Boolean hypercube is a small-set expander. Isn't this equivalent to giving an affirmative answer to the SSEH for the Boolean n-hypercube instance?  
> **username_0**: This is what I would guess be said as "giving a degree-4 SOS certificate" for the Boolean n-hypercube being a small-set expander. And this is supposed to be surprising since the Boolean n-hypercube is a hard-case of UGC?  
> **username_0**: @SashoNikolov I am not getting what is wrong about the phrase ``SSEH on the hypercube". SSEH is a statement of the form "Given a regular graph xyz decision question is hard" - So why doesn't it make sense to say that theorem 2.8 and Lemma 2.10 of Barak's notes imply that "On the Boolean hypercube the xyz decision question is easy" - which is what I would mean by saying that "SSEH on the Boolean hypercube is easy" - what is wrong here?  
> **username_1**: There is only one instance of the hypercube graph for each power of 2. Such sparse problems are always unlikely to be hard. Moreover, since each such instance is a small set expander, the trivial algorithm that always outputs yes solves the problem on the hypercube. So sure, the problem is easy on the hypercube, but it's weird to consider a problem only on a very sparse set of yes-only instances. And you don't need SoS to show that it's easy. It **is** interesting that the hypercube is easy for SoS, but the reason is that this is an **ingredient** in solving a much bigger set of instances.  
> **username_0**: Thanks! What is the much bigger/non-sparse set of instances for which a similar degree-4 SOS certificate for the small-set expansion hypothesis exists? (for which apparently the proof on the hypercube is an ingredient!)  
> **username_1**: The ones in Theorem 6.1. in http://arxiv.org/pdf/1205.4484v3.pdf  
> **username_0**: Is this the same as the claim that the UGC on the "noisy cube" has an efficient deg-4 SOS certificate? Or is that something else?  

---

