A note on Unique Games

We give a tighter analysis of the algorithm of Khot [S. Khot, On the power of unique 2-prover 1-round games, in: Proceedings of the 34th Annual ACM Symposium on Theory of Computing, Montreal, Quebec, Canada, 2002, pp. 767–775] which shows that given a unique 2-prover-1-round game with value 1−ε, one can find in polynomial time an assignment to the game with an expected weight of , where k is the size of the answer domain. This shows that if the Unique Games Conjecture is true then the domain size k, must be at least Ω((ε1/6log1/3−1(1/ε))), which is an improvement over the previous Ω((ε1/10log1/4−1(1/ε))) bound.