Unique Games Over Integers
journal contributionposted on 01.09.1993 by Ryan O'Donnell, Yi Wu, Yuan Zhou
Any type of content formally published in an academic journal, usually following a peer-review process.
Consider systems of two-variable linear equations of the form xi−xj = cij , where the cij ’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