Streaming Hardness of Unique Games
Streaming Hardness of Unique Games
复制标题
独特游戏的流媒体硬度
DOI：
10.4230/lipics.approx-random.2019.5
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Runzhou Tao
中科院分区：
文献类型：
--
作者：
V. Guruswami;Runzhou Tao
我们研究了流模型中唯一游戏实例的近似值问题。一个简单的计数的数量的约束除以$p$，字母大小的唯一游戏，给出一个平凡的$p$-近似，可以计算在$O（\log n）$空间。同时，以高概率，$\tilde{O}（n）$约束的样本足以估计最优值到$（1+\n）$精度。我们证明了任何单通道流算法，实现$（p-\n）$-近似需要$\Omega_\n（\sqrt{n}）$空间。我们的证明是通过减少从下界的通信问题，这是一个$p$-ary变量的布尔隐藏匹配问题在文献中研究。考虑到独特的游戏作为一个起点，减少其他优化问题的效用，我们的强大的硬度近似独特的游戏可能会导致下流的硬度结果为其他CSP类似的问题。
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.