产品分布的通信复杂性

Question

一般来说（双方）设置长度n的输入问题n，我们知道各方需要通信 $ \ oomga（n）$ 。令人惊讶的是，今天我发现了（如果我理解正确），这对于产品分布而言，这不是真正的，即，当Alice的和Bob的投入独立于任意分布时选择。在这个 paper ，它们提供了一个通信复杂度 $ \ mathcal {o}（\ sqrt {n} \ log（1 / \ epsilon））$ ，其中 $ \ epsilon $ 是一些错误术语与此处的问题无关。 现在我很好奇关于其他众所周知的通信复杂性问题是否存在空白。

问题：当一个人认为任意输入分布和产品分布时，其他众所周知的问题在通信复杂性之间表现出差距。内部产品或交叉点是否有类似的结果？

Answer 1

设置差异对于产品分布而言更容易，因为设置差分的硬分配远非作为产品分布。从硬发行版 $（x，y）$ for Inner产品中，我们需要什么？我们希望 $ x，y $ 单独存在，我们想要 $ x \ cdot y $ 大多数为零，说 $ x \ cdot y $ 包含大多数单个 $ 1 $ 。这不能通过产品分布来实现。虽然您可以获得 $ x \ cdot y $ 属性，但这意味着两个输入中的每一个都非常偏见。相反，如果输入 $ x，y $ 是非常随机的，那么 $ x \ cdot y $ 将有许多 $ 1 $ s。

内部产品功能不会遭受同一问题。实际上，似乎最艰难的分布是均匀分布。您可以使用差异方法证明线性下限 - 这是标准的，并使用称为 Lindsey的引理的差异的界限。

sherstov在他的论文中提出了一个最佳的差距例子产品和非产品分布下的通信复杂性。他的功能是一个随机函数，选择，使得没有大的单色 $ 1 $ -rectangles。最终结果是一个函数，其随机通信复杂性是 $ \ oomega（n）$ ，但对于任何产品分发，随机通信复杂性是 $ O（1）$ 。