2026-08-07T04:58:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11220 2024-03-06T10:47:43Z ddc:004 open_access

Streaming Hardness of Unique Games Guruswami, Venkatesan Tao, Runzhou Communication complexity CSP Fourier Analysis Lower bounds Streaming algorithms Unique Games 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+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 downstream hardness results for streaming approximability for other CSP-like problems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Venkatesan Guruswami and Runzhou Tao 2019 Is Part Of LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2019.5 urn:nbn:de:0030-drops-112209 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.5 eng https://creativecommons.org/licenses/by/3.0/legalcode