  We show that NP-hardness of approximating Boolean unique games on small set
expanders can be amplified to the full Unique Games Conjecture on small set
expanders. The latter conjecture is known to imply hardness results for
problems like Balanced-Separator, Minimum-Linear-Rearrangement and
Small-Set-Expansion that are not known under the Unique Games Conjecture. Our
result follows from: (1) A transformation that fortifies any unique game on a
small set expander. (2) An improved parallel repetition theorem for fortified
games on small set expanders. Our approach avoids the known limitation on
strong parallel repetition of unique games by enlarging the alphabet
considerably before repetition. The limitation does not hold for unique games
with a sufficiently large alphabet. Prior to this work, parallel repetition
from fortification was only known for projection games, and seemed hopeless for
unique games. Perhaps surprisingly, the idea for fortification of unique games
comes from a reduction of Raghavendra and Steurer from Small-Set-Expansion to
Unique Games.
