file.pdf (225.5 kB)

Unique Games Over Integers

Download (225.5 kB)
journal contribution
posted on 01.09.1993, 00:00 by Ryan O'Donnell, Yi Wu, Yuan Zhou
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