A simple proof of a new set disjointness with applications to data streams
A simple proof of a new set disjointness with applications to data streams
复制标题
DOI：
10.4230/lipics.ccc.2021.37
复制
发表时间：
2021-05
期刊：
影响因子：
--
通讯作者：
Akshay Kamath;Eric Price;David P. Woodruff
中科院分区：
文献类型：
--
作者：
Akshay Kamath;Eric Price;David P. Woodruff
多层承诺集的不相交性是应用中通信复杂性最广泛的问题之一。在这个问题中，有k个参与者，其子集为S1，...，Sk，每个从{1，2，.，n}，并且我们被保证要么集合是（1）成对不相交的，要么（2）存在唯一元素j出现在所有集合中，否则它们是成对不相交的。在黑板模型中，以恒定概率求解该问题的总通信量为Ω（n/k）。我们观察到，对于大多数应用，我们只需要看看我们所谓的“大多数”集合不相交性问题，它改变了情况（2），说至少有一半的集合中出现了唯一的元素j，否则集合是不相交的。这种变化给了我们一个更简单的证明Ω（n/k）随机总通信下界，避免了Hellinger距离和Poincare不等式。我们的证明也给出了强下界的高概率协议，这是远远大于可能的集合不相交问题。利用这一点，我们展示了几个新的结果数据流：1。对于ε-ε 2-Heavy Hitters，用于检测是否存在ε-ε 2-Heavy Hitters的仅插入模型中的任何O（1）遍流算法都需要[EQUATION]位的存储器，这是最佳的log n因子。对于确定性算法和常数ε，这给出了Ω（n1/2）下界，改进了先前的Ω（log n）下界。我们还得到了Zipfian分布的下界。2.对于NXP-估计，p > 2，我们给出了一个O（1）-通过Ω（n1−2/p log（1/δ））位下界，用于在仅插入模型中输出概率为1 − δ的O（1）-近似。这是最优的，之前最好的下界是Ω（n1−2/p + log（1/δ））。3.对于RdXn中稀疏矩阵的低秩近似，如果我们在行序模型中一次看到一个矩阵的行，每行具有O（1）个非零项，则任何确定性算法都需要[EQUATION]内存来输出O（1）-近似秩-1近似。最后，我们考虑严格的和一般的旋转栅门流模型，并显示分离之间的素描下界和非素描上界的沉重打击者的问题。
The multiplayer promise set disjointness is one of the most widely used problems from communication complexity in applications. In this problem there are k players with subsets S1, ..., Sk, each drawn from {1, 2,..., n}, and we are promised that either the sets are (1) pairwise disjoint, or (2) there is a unique element j occurring in all the sets, which are otherwise pairwise disjoint. The total communication of solving this problem with constant probability in the blackboard model is Ω(n/k). We observe for most applications, it instead suffices to look at what we call the "mostly" set disjointness problem, which changes case (2) to say there is a unique element j occurring in at least half of the sets, and the sets are otherwise disjoint. This change gives us a much simpler proof of an Ω(n/k) randomized total communication lower bound, avoiding Hellinger distance and Poincare inequalities. Our proof also gives strong lower bounds for high probability protocols, which are much larger than what is possible for the set disjointness problem. Using this we show several new results for data streams: 1. for ℓ2-Heavy Hitters, any O(1)-pass streaming algorithm in the insertion-only model for detecting if an ε-ℓ2-heavy hitter exists requires [EQUATION] bits of memory, which is optimal up to a log n factor. For deterministic algorithms and constant ε, this gives an Ω(n1/2) lower bound, improving the prior Ω(log n) lower bound. We also obtain lower bounds for Zipfian distributions. 2. for ℓp-Estimation, p > 2, we show an O(1)-pass Ω(n1−2/p log(1/δ)) bit lower bound for outputting an O(1)- approximation with probability 1 − δ, in the insertion-only model. This is optimal, and the best previous lower bound was Ω(n1−2/p + log(1/δ)). 3. for low rank approximation of a sparse matrix in RdXn, if we see the rows of a matrix one at a time in the row-order model, each row having O(1) non-zero entries, any deterministic algorithm requires [EQUATION] memory to output an O(1)-approximate rank-1 approximation. Finally, we consider strict and general turnstile streaming models, and show separations between sketching lower bounds and non-sketching upper bounds for the heavy hitters problem.