1
$\begingroup$
  • 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"?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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. 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.

Improve this answer
$\endgroup$
17
  • $\begingroup$ 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? $\endgroup$
    – Student
    Commented Mar 31, 2015 at 19:13
  • $\begingroup$ (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"?) $\endgroup$
    – Student
    Commented Mar 31, 2015 at 19:17
  • 1
    $\begingroup$ 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? $\endgroup$
    – user6818
    Commented Mar 31, 2015 at 23:05
  • 1
    $\begingroup$ 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. $\endgroup$
    – Sasho Nikolov
    Commented Apr 2, 2015 at 21:35
  • 1
    $\begingroup$ The ones in Theorem 6.1. in arxiv.org/pdf/1205.4484v3.pdf $\endgroup$
    – Sasho Nikolov
    Commented Apr 3, 2015 at 0:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.