Elena Gribelyuk will present her General Exam "Lower Bounds for Adversarially Robust Streaming" on 5/17/2024 at 8am in CS 302 and Zoom. Zoom link: [ https://princeton.zoom.us/j/2559568276 | https://princeton.zoom.us/j/2559568276 ] Committee members: Huacheng Yu (adviser), Alex Lombardi, and Gillat Kol Reading list and abstract: [ https://docs.google.com/document/d/1II1zg-GOCtRX2CZDaO3XebeeHy5XkNnOquyiTppx... | https://docs.google.com/document/d/1II1zg-GOCtRX2CZDaO3XebeeHy5XkNnOquyiTppx... ] Abstract: The majority of streaming problems are defined and analyzed in a static setting, where the data stream is fixed in advance to be a fixed sequence of insertions and deletions. However, many real world applications require a more flexible model, where an adaptive adversary may select future stream elements after observing the previous outputs of the algorithm. Over the last few years, there has been increased interest in proving lower bounds for natural problems in the adaptive streaming model. In this work, we give the first known adaptive attack against linear sketches for the well-studied L0-estimation problem over turnstile, integer streams. For any linear streaming algorithm which uses an integer r x n sketching matrix A, this attack makes O(r^8) queries and succeeds with high constant probability in breaking the sketch. Additionally, we give an adaptive attack against linear sketches for the L0-estimation problem over finite fields F_p, which requires a smaller number of O(r^3) queries. Our results provide an exponential improvement over the previous number of adaptive queries known to break an L0-estimation