Relaxed Models for Adversarial Streaming: The Advice Model and the Bounded Interruptions Model

Menachem Sadigurschi, Moshe Shechner, Uri Stemmer

Streaming algorithms are typically analyzed in the oblivious setting, where we assume that the input stream is fixed in advance. Recently, there is a growing interest in designing…