A Framework for Adversarially Robust Streaming Algorithms
A Framework for Adversarially Robust Streaming Algorithms
复制标题
DOI：
10.1145/3471485.3471488
复制
发表时间：
2020-03
期刊：
影响因子：
--
通讯作者：
Omri Ben-Eliezer;Rajesh Jayaram;David P. Woodruff;E. Yogev
中科院分区：
文献类型：
--
作者：
Omri Ben-Eliezer;Rajesh Jayaram;David P. Woodruff;E. Yogev
我们研究流算法的对抗鲁棒性。在此背景下，如果一个算法的性能保证即使在流是由一个对手自适应选择的情况下仍然成立，那么该算法就被认为是鲁棒的。这个对手会沿着流观察算法的输出，并能以在线的方式做出反应。虽然确定性流算法本身是鲁棒的，但流文献中的许多核心问题并不存在亚线性空间的确定性算法；另一方面，针对这些问题的经典的节省空间的随机算法通常不具有对抗鲁棒性。这就自然引出了一个问题：对于这些问题，是否存在高效的具有对抗鲁棒性的（随机）流算法。
We investigate the adversarial robustness of streaming algorithms. In this context, an algorithm is considered robust if its performance guarantees hold even if the stream is chosen adaptively by an adversary that observes the outputs of the algorithm along the stream and can react in an online manner. While deterministic streaming algorithms are inherently robust, many central problems in the streaming literature do not admit sublinear-space deterministic algorithms; on the other hand, classical space-efficient randomized algorithms for these problems are generally not adversarially robust. This raises the natural question of whether there exist efficient adversarially robust (randomized) streaming algorithms for these problems.