3 papers
cs.DS2022
Streaming algorithms for the missing item finding problem
Manuel Stoeckl
Many problems on data streams have been studied at two extremes of difficulty: either allowing randomized algorithms, in the static setting (where they should err with bounded prob…
cs.DS2021
Adversarially Robust Coloring for Graph Streams
Amit Chakrabarti, Prantar Ghosh, Manuel Stoeckl
A streaming algorithm is considered to be adversarially robust if it provides correct outputs with high probability even when the stream updates are chosen by an adversary who may…
cs.CC2021
The Element Extraction Problem and the Cost of Determinism and Limited Adaptivity in Linear Queries
Amit Chakrabarti, Manuel Stoeckl
Two widely-used computational paradigms for sublinear algorithms are using linear measurements to perform computations on a high dimensional input and using structured queries to a…