Dynamic algorithms against an adaptive adversary: generic constructions and lower bounds
Dynamic algorithms against an adaptive adversary: generic constructions and lower bounds
复制标题
DOI：
10.1145/3519935.3520064
复制
发表时间：
2021-11
期刊：
影响因子：
--
通讯作者：
A. Beimel;Haim Kaplan;Y. Mansour;Kobbi Nissim;Thatchaphol Saranurak;Uri Stemmer
中科院分区：
文献类型：
--
作者：
A. Beimel;Haim Kaplan;Y. Mansour;Kobbi Nissim;Thatchaphol Saranurak;Uri Stemmer
给定一个经历一系列更新的输入，动态算法在任何时间点都保持某个预定义问题的有效解决方案;目标是设计一种算法，在该算法中计算更新输入的解决方案比从头开始计算解决方案更有效。针对自适应对手的动态算法要求在对手看到算法的前一次输出后选择下一次更新时是正确的。我们获得了更快的动态算法对自适应对手和分离的结果是什么是可以实现的遗忘与自适应设置。为了得到这些结果，我们利用差分隐私，密码学和自适应数据分析技术。我们的结果如下。1.我们给出了一个通用的约简，将一个对抗不经意对手的动态算法转化为一个对自适应对手具有鲁棒性的动态算法。这种减少维护了几个不经意算法的副本，并使用差分隐私来保护它们的随机位。使用这种减少，我们获得动态算法对自适应对手的改进更新和查询时间的全球最小切割，所有对的距离，和所有对有效的阻力。2.我们进一步提高我们的更新和查询时间，展示了如何维护一个稀疏的扩展分解，可以快速刷新。这种快速刷新使它能够抵御我们所说的闪烁对手，这种对手只能在刷新后观察算法的输出。我们相信，这些技术将被证明是有用的其他问题。3.另一方面，我们指定的动态问题，假设一个随机的预言，每一个动态算法，解决他们对自适应对手必须多项式慢于一个相当简单的动态算法，解决他们对一个不经意的对手。我们首先显示搜索问题的分离结果，然后显示估计问题的分离结果。在后一种情况下，我们的分离结果来自自适应数据分析的下限。
Given an input that undergoes a sequence of updates, a dynamic algorithm maintains a valid solution to some predefined problem at any point in time; the goal is to design an algorithm in which computing a solution to the updated input is done more efficiently than computing the solution from scratch. A dynamic algorithm against an adaptive adversary is required to be correct when the adversary chooses the next update after seeing the previous outputs of the algorithm. We obtain faster dynamic algorithms against an adaptive adversary and separation results between what is achievable in the oblivious vs. adaptive settings. To get these results we exploit techniques from differential privacy, cryptography, and adaptive data analysis. Our results are as follows. 1. We give a general reduction transforming a dynamic algorithm against an oblivious adversary to a dynamic algorithm robust against an adaptive adversary. This reduction maintains several copies of the oblivious algorithm and uses differential privacy to protect their random bits. Using this reduction we obtain dynamic algorithms against an adaptive adversary with improved update and query times for global minimum cut, all pairs distances, and all pairs effective resistance. 2. We further improve our update and query times by showing how to maintain a sparsifier over an expander decomposition that can be refreshed fast. This fast refresh enables it to be robust against what we call a blinking adversary that can observe the output of the algorithm only following refreshes. We believe that these techniques will prove useful for additional problems. 3. On the flip side, we specify dynamic problems that, assuming a random oracle, every dynamic algorithm that solves them against an adaptive adversary must be polynomially slower than a rather straightforward dynamic algorithm that solves them against an oblivious adversary. We first show a separation result for a search problem and then show a separation result for an estimation problem. In the latter case our separation result draws from lower bounds in adaptive data analysis.