2018/11/12 by Venkatesan Guruswami, Runzhou Tao
Computer Science · Mathematics · #Alphabet #Approximation algorithm #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Cryptography and Data Security #Discrete mathematics #Hardness of approximation #Matching (statistics) #Mathematics #Optimization and Search Problems #Point (geometry) #Reduction (mathematics) #Sample complexity #Simple (philosophy) #Space (punctuation) #Statistics #Streaming algorithm #Upper and lower bounds #Value (mathematics) #cs.CC #cs.DS
paper · pdf · doi:10.4230/lipics.approx-random.2019.5
arxiv created 2018/11/12 · openalex publication_date 2018/11/12 · openalex created_date 2018/11/16 · arxiv updated 2020/11/13 · openalex updated_date 2026/08/05
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 O(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.