Streaming algorithms are typically analyzed in the oblivious setting, where we assume that the input stream is fixed in advance. Recently, there is a growing interest in designing adversarially robust streaming algorithms that must maintain utility even when the input stream is chosen adaptively and adversarially as the execution progresses. While several fascinating results are known for the adversarial setting, in general, it comes at a very high cost in terms of the required space. Motivated by this, in this work we set out to explore intermediate models that allow us to interpolate between the oblivious and the adversarial models. Specifically, we put forward the following two models: (1) *The advice model*, in which the streaming algorithm may occasionally ask for one bit of advice. (2) *The bounded interruptions model*, in which we assume that the adversary is only partially adaptive. We present both positive and negative results for each of these two models. In particular, we present generic reductions from each of these models to the oblivious model. This allows us to design robust algorithms with significantly improved space complexity compared to what is known in the plain adversarial model.
翻译:流动算法通常在隐蔽的环境中分析, 我们假设输入流是事先固定的。 最近, 人们越来越有兴趣设计对抗性强的流算法, 即使在输入流随着执行进展而选择时, 也必须保持实用性。 虽然对敌对环境来说有几个令人着迷的结果是众所周知的, 一般来说, 从所需的空间来看, 它的成本非常高。 受此启发, 我们在此工作中开始探索中间模型, 使我们能够在隐蔽和对抗模式之间进行相互交错。 具体地说, 我们提出了以下两种模型:(1) * 咨询模型*, 流动算法有时会要求一点建议。 (2) * 连接中断模式*, 我们假设对立方只是部分的适应性。 我们对这两种模型中的每一种模型都提出了正反两方面的结果。 我们特别提出了从这些模型中每一种模型到模糊模型的通用的减少值。 这使我们能够设计强大的算法,大大改进了空间复杂性,与平坦的对抗模型所知道的一样。