Questions tagged [unique-games-conjecture]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3
votes
1answer
393 views

Consequences of Unique Games being a NPI problem

Assume that UG is $\mathsf{NPI}$, i.e. not solvable in $\mathsf{P}$ nor in $\mathsf{NP\text{-}complete}$ (so UGC is false). Is it still NP-hard to give a $(2-\epsilon)$ polytime approximation ...
3
votes
1answer
464 views

What is a "level-r pseudo expectation functional"?

In the context of the SOS hierarchy papers, it seems that a "level-r psuedo expectation functional" is the same as an operator taking expectations of functions just that this one has the restriction ...
1
vote
1answer
581 views

The Goemans-Williamson algorithm in the $SOS$ framework

If there is a variable $x_i$ for every vertex $i$ of a $d$-regular graph $G$ then assigning $x_i = \pm 1$ gives a cut, say $(S,\bar{S})$, of the graph. We can then see that, $\langle x,L x\rangle$, ...