论文标题
具有随机订购约束的CSP的流式传输复杂性
Streaming complexity of CSPs with randomly ordered constraints
论文作者
论文摘要
当约束以随机顺序到达时，我们开始研究约束满意度问题（CSP）流的复杂性。我们证明存在一个CSP，即$ \ textsf {max-dicut} $，为此，随机排序可证明有所不同。 $ 4/9 \ $ \ textsf {diCut} $的近似值约为$ \ textsf {dicut} $需要$ω（\ sqrt {n}）$带有对抗订购的空间，我们表明，随机订购的约束时，存在$ 0.48 $ -approximation algorximation algorith algorith a $ o（$ o）我们还为对抗订购设置的变体提供了$ \ textsf {max-dicut} $的新算法。具体来说，我们给出了一个两通 - $ O（\ log n）$ space $ 0.48 $ -Approximation算法，用于一般图形和一个单通$ \ tilde {o}（\ sqrt {n}）$ 0.48 $ 0.48 $ - APPROXIMATION ALGORITAL for BOINDED ALGORITHM for BOINDED BENDED LEMAGE图。 负面的一面，我们证明，约束的满足分配支持单明智的独立分布需要$ω（\ sqrt {n}）$ - 即使在约束随机订购时，CSP都需要$ω（\ sqrt {n}）$ - 空间。以前仅以对抗有序的约束而闻名。将结果扩展到随机排序的约束需要将硬实例从随机匹配的结合切换为简单的Erdös-Renyi随机图（超级）图，并扩展可以在此类实例上执行傅立叶分析的工具。 先前使用随机排序考虑的唯一CSP是$ \ textsf {max-cut} $，其中不知道订购以更改近似性。具体而言，对于$ o（\ sqrt {n}）$ space算法而言，它与对抗订购一样，很难用随机排序进行近似值。我们的结果表明，各种可能性的种类繁多，并激发了对CSP的进一步研究，并随机有序约束。
We initiate a study of the streaming complexity of constraint satisfaction problems (CSPs) when the constraints arrive in a random order. We show that there exists a CSP, namely $\textsf{Max-DICUT}$, for which random ordering makes a provable difference. Whereas a $4/9 \approx 0.445$ approximation of $\textsf{DICUT}$ requires $Ω(\sqrt{n})$ space with adversarial ordering, we show that with random ordering of constraints there exists a $0.48$-approximation algorithm that only needs $O(\log n)$ space. We also give new algorithms for $\textsf{Max-DICUT}$ in variants of the adversarial ordering setting. Specifically, we give a two-pass $O(\log n)$ space $0.48$-approximation algorithm for general graphs and a single-pass $\tilde{O}(\sqrt{n})$ space $0.48$-approximation algorithm for bounded degree graphs. On the negative side, we prove that CSPs where the satisfying assignments of the constraints support a one-wise independent distribution require $Ω(\sqrt{n})$-space for any non-trivial approximation, even when the constraints are randomly ordered. This was previously known only for adversarially ordered constraints. Extending the results to randomly ordered constraints requires switching the hard instances from a union of random matchings to simple Erdös-Renyi random (hyper)graphs and extending tools that can perform Fourier analysis on such instances. The only CSP to have been considered previously with random ordering is $\textsf{Max-CUT}$ where the ordering is not known to change the approximability. Specifically it is known to be as hard to approximate with random ordering as with adversarial ordering, for $o(\sqrt{n})$ space algorithms. Our results show a richer variety of possibilities and motivate further study of CSPs with randomly ordered constraints.
