6 papers
Finding missing items requires strong forms of randomness
Amit Chakrabarti, Manuel Stoeckl
Adversarially robust streaming algorithms are required to process a stream of elements and produce correct outputs, even when each stream element can be chosen as a function of ear…
Low-Memory Algorithms for Online and W-Streaming Edge Coloring
Prantar Ghosh, Manuel Stoeckl
For edge coloring, the online and the W-streaming models seem somewhat orthogonal: the former needs edges to be assigned colors immediately after insertion, typically without any s…
Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms
Sepehr Assadi, Amit Chakrabarti, Prantar Ghosh +1
In recent years, there has been a growing interest in solving various graph coloring problems in the streaming model. The initial algorithms in this line of work are all crucially…
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…
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…
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…