Skip to main content

Questions tagged [unique-games-conjecture]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3 votes
1 answer
596 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 ...
user6818's user avatar
  • 281
3 votes
1 answer
408 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 ...
NicosM's user avatar
  • 47
1 vote
1 answer
670 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$, ...
user6818's user avatar
  • 281