  We study the problem of approximating the value of a Unique Game instance in
the streaming model. A simple count of the number of constraints divided by
$p$, the alphabet size of the Unique Game, gives a trivial $p$-approximation
that can be computed in $O(\log n)$ space. Meanwhile, with high probability, a
sample of $\tilde{O}(n)$ constraints suffices to estimate the optimal value to
$(1+\epsilon)$ accuracy. We prove that any single-pass streaming algorithm that
achieves a $(p-\epsilon)$-approximation requires $\Omega_\epsilon(\sqrt{n})$
space. Our proof is via a reduction from lower bounds for a communication
problem that is a $p$-ary variant of the Boolean Hidden Matching problem
studied in the literature. Given the utility of Unique Games as a starting
point for reduction to other optimization problems, our strong hardness for
approximating Unique Games could lead to down\emph{stream} hardness results for
streaming approximability for other CSP-like problems.
