论文标题
白色框对面数据流模型
The White-Box Adversarial Data Stream Model
论文作者
论文摘要
我们研究了白框对抗模型中的流算法，在该模型中，在每个时间步骤中观察算法的整个内部状态的对手会自适应地选择流。我们表明，非平凡算法仍然是可能的。我们首先为$ l_1 $ heavy的击球手问题提供了随机算法，该问题的表现优于长流上最佳的确定性Misra-Gries算法。如果白色框对手是计算界限的，我们使用加密技术来进一步减少我们$ L_1 $的击球手算法的记忆，并为图形，字符串和线性代数问题设计许多其他算法。这种算法的存在令人惊讶，因为流算法在该模型中甚至没有一个秘密键，即其状态是对手的完全了解的。我们设计的一种算法是用于估计流中有插入和删除的流中不同元素的数量，从而实现了乘法近似和sublerear空间。对于确定性算法，这种算法是不可能的。 我们还提供了一条通用技术，该技术将任何两个播放器确定性通信的下限转换为{\ it随机}算法的下界，向白盒对手鲁棒。特别是，我们的结果表明，对于所有$ p \ ge 0 $，存在一个常数的$ c_p> 1 $，以便任何$ c_p $ - approximation算法for $ f_p $ tom tom矩估计仅在插入流中具有白盒对手的插入流中，需要$ω（n）$ $ω（n）$ space of n $ n $ n $ n $ n $ n $ n $。同样，有一个常数的$ c> 1 $，以便在矩阵等级的仅插入流中的任何$ c $ approximation算法都需要$ω（n）$空间，并带有白盒对手。因此，我们基于密码学的算法结果显示了计算界限和无限对手之间的分离。 （抽象缩短以达到Arxiv限制。）
We study streaming algorithms in the white-box adversarial model, where the stream is chosen adaptively by an adversary who observes the entire internal state of the algorithm at each time step. We show that nontrivial algorithms are still possible. We first give a randomized algorithm for the $L_1$-heavy hitters problem that outperforms the optimal deterministic Misra-Gries algorithm on long streams. If the white-box adversary is computationally bounded, we use cryptographic techniques to reduce the memory of our $L_1$-heavy hitters algorithm even further and to design a number of additional algorithms for graph, string, and linear algebra problems. The existence of such algorithms is surprising, as the streaming algorithm does not even have a secret key in this model, i.e., its state is entirely known to the adversary. One algorithm we design is for estimating the number of distinct elements in a stream with insertions and deletions achieving a multiplicative approximation and sublinear space; such an algorithm is impossible for deterministic algorithms. We also give a general technique that translates any two-player deterministic communication lower bound to a lower bound for {\it randomized} algorithms robust to a white-box adversary. In particular, our results show that for all $p\ge 0$, there exists a constant $C_p>1$ such that any $C_p$-approximation algorithm for $F_p$ moment estimation in insertion-only streams with a white-box adversary requires $Ω(n)$ space for a universe of size $n$. Similarly, there is a constant $C>1$ such that any $C$-approximation algorithm in an insertion-only stream for matrix rank requires $Ω(n)$ space with a white-box adversary. Our algorithmic results based on cryptography thus show a separation between computationally bounded and unbounded adversaries. (Abstract shortened to meet arXiv limits.)
