Streaming Hardness of Unique Games
share
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( n) space. Meanwhile, with high probability, a sample of Õ(n) constraints suffices to estimate the optimal value to (1+ϵ) accuracy. We prove that any single-pass streaming algorithm that achieves a (p-ϵ)-approximation requires Ω_ϵ(√(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 downstream hardness results for streaming approximability for other CSP-like problems.
READ FULL TEXT