Dynamic Algorithms Against an Adaptive Adversary: Generic Constructions and Lower Bounds

Understand

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.