Bounds on Linear Unique Game value

87 Views Asked by At

Suppose we have a system of $N$ linear equations in $\mathbb{Z}_n$ of the form $x_i - x_j = c_{ij}$ where the $x_i$ are variables and the $c_{ij}$ are constants.

Suppose that at most $M$ of these equations can be satisfied at once and that $M/N = \beta$

Now there is a game where there are two contestants, $P_1$ and $P_2$. $P_1$ and $P_2$ can collude but they cannot communicate once the game starts. The game selects an equation at random, and tells $P_1$ the index of the first variable $i$ and $P_2$ the index of the second variable $j$. $P_1$ and $P_2$ respond with values for $x_i$ and $x_j$ respectively, and they win if $x_i - x_j = c_{ij}$

There is an "obvious" fact that the best strategy wins with a probability of at most $\max\{4\beta, 1\} $, except I don't see why the $4\beta$ part is so obvious.

(The statement comes from http://cs.nyu.edu/~khot/papers/icm-khot.pdf page 6)