Transformers are slow and memory-hungry on long sequences, since the time and memory
complexity of self-attention are quadratic in sequence length. Approximate attention …

Abstract Methods for Approximate Query Processing (AQP) are essential for dealing with
massive data. They are often the only means of providing interactive response times when …

We introduce a new sublinear space data structure—the count-min sketch—for summarizing
data streams. Our sketch allows fundamental queries in data stream summarization such as …

In the data stream scenario, input arrives very rapidly and there is limited memory to store
the input. Algorithms have to work with one or few passes over the data, space less than …

Large-scale genomics demands computational methods that scale sublinearly with the
growth of data. We review several data structures and sketching techniques that have been …

We give the first optimal algorithm for estimating the number of distinct elements in a data
stream, closing a long line of theoretical research on this problem begun by Flajolet and …

We investigate the adversarial robustness of streaming algorithms. In this context, an
algorithm is considered robust if its performance guarantees hold even if the stream is …

We introduce a new sublinear space data structure—the Count-Min Sketch—for
summarizing data streams. Our sketch allows fundamental queries in data stream …

In the adversarially robust streaming model, a stream of elements is presented to an
algorithm and is allowed to depend on the output of the algorithm at earlier times during the …

We prove an optimal Ω (n) lower bound on the randomized communication complexity of the
much-studied Gap-Hamming-Distance problem. As a consequence, we obtain essentially …