Separating Adaptive Streaming from Oblivious Streaming

We present a streaming problem for which every adversarially-robust streaming algorithm must use polynomial space, while there exists a classical (oblivious) streaming algorithm that uses only polylogarithmic space. This results in a strong separation between oblivious and adversarially-robust streaming algorithms.