论文标题
通过Vapnik-Chervonenkis维度的镜头的脱节：稀疏及以后
Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond
论文作者
论文摘要
脱节问题 - 在给爱丽丝和鲍勃的两个子集$ \ {1，\ dots，n \} $的情况下，他们必须检查他们的集合是否相交 - 是通信复杂性的核心问题。尽管已知该问题的确定性和随机通信复杂性都为$θ（n）$，但也众所周知，如果假定将集合从某些受限制的集合系统中绘制出来，那么通信复杂性可能会较低。在这项工作中，我们探讨了沟通复杂性如何根据基础设定系统的复杂性发生变化。我们在这项工作中使用的设定系统的复杂度度量是Vapnik-Chervonenkis（VC）维度。更确切地说，在任何具有$ d $界限的VC尺寸的设置系统上，我们分析了确定性和随机通信复杂性的大小，这是$ d $和$ n $的函数。 在本文中，我们构建了VC尺寸$ D $的两个自然集合系统，这些系统是由几何学动机的。使用这些集合系统，我们表明，确定性和随机通信复杂性可以为$ \widetildeθ\ left（d \ log \ left（n/d \ right）\ right）$ for VC dimension $ d $的集合系统，这与VC尺寸$ d $的所有集合系统的确定性上限匹配。当集合属于有界VC维度的集合系统时，我们还研究了集体交叉点问题的确定性和随机通信复杂性。我们表明，存在VC尺寸$ D $的设置系统，因此，对于设定的相交问题而言，确定性和随机和随机（单向和多轮）的复杂性可能高至$θ\ left（d \ log \ left（n/d \ weled（n/d \ right）\ right）$，并且在所有设置的VC Dimension Remension $ d $ d $中都紧密。
The disjointness problem - where Alice and Bob are given two subsets of $\{1, \dots, n\}$ and they have to check if their sets intersect - is a central problem in the world of communication complexity. While both deterministic and randomized communication complexities for this problem are known to be $Θ(n)$, it is also known that if the sets are assumed to be drawn from some restricted set systems then the communication complexity can be much lower. In this work, we explore how communication complexity measures change with respect to the complexity of the underlying set system. The complexity measure for the set system that we use in this work is the Vapnik-Chervonenkis (VC) dimension. More precisely, on any set system with VC dimension bounded by $d$, we analyze how large can the deterministic and randomized communication complexities be, as a function of $d$ and $n$. In this paper, we construct two natural set systems of VC dimension $d$, motivated from geometry. Using these set systems we show that the deterministic and randomized communication complexity can be $\widetildeΘ\left(d\log \left( n/d \right)\right)$ for set systems of VC dimension $d$ and this matches the deterministic upper bound for all set systems of VC dimension $d$. We also study the deterministic and randomized communication complexities of the set intersection problem when sets belong to a set system of bounded VC dimension. We show that there exists set systems of VC dimension $d$ such that both deterministic and randomized (one-way and multi-round) complexity for the set intersection problem can be as high as $Θ\left( d\log \left( n/d \right) \right)$, and this is tight among all set systems of VC dimension $d$.
