Unique Games Over Integers

Consider systems of two-variable linear equations of the form x_i−x_j = c_ij , where the c_ij ’s are integer constants. We show that even if there is an integer solution satisfying at least a (1 −ε)- fraction of the equations, it is Unique-Games-hard to find an integer (or even real) solution satisfying at least an ε-fraction of the equations. Indeed, we show it is Unique-Games-hard even to find an ε-good solution modulo any integer m ≥ m0(ε) of the algorithm’s choosing