58 citations · 104 across the 15 of their papers we have counts for
21 papers
Robust Streaming Against Low-Memory Adversaries
Omri Ben-Eliezer, Krzysztof Onak, Sandeep Silwal
Robust streaming, the study of streaming algorithms that provably work when the stream is generated by an adaptive adversary, has seen tremendous progress in recent years. However,…
Adversarially Robust Streaming via Dense--Sparse Trade-offs
Omri Ben-Eliezer, Talya Eden, Krzysztof Onak
A streaming algorithm is adversarially robust if it is guaranteed to perform correctly even in the presence of an adaptive adversary. Recently, several sophisticated frameworks for…
Dynamic Graph Algorithms with Batch Updates in the Massively Parallel Computation Model
Krzysztof Nowicki, Krzysztof Onak
We study dynamic graph algorithms in the Massively Parallel Computation model, which was inspired by practical data processing systems. Our goal is to provide algorithms that can e…
Scalable Fair Clustering
Arturs Backurs, Piotr Indyk, Krzysztof Onak +3
We study the fair variant of the classic -median problem introduced by Chierichetti et al. [2017]. In the standard -median problem, given an input pointset , the goal is t…
Fully Dynamic MIS in Uniformly Sparse Graphs
Krzysztof Onak, Baruch Schieber, Shay Solomon +1
We consider the problem of maintaining a maximal independent set (MIS) in a dynamic graph subject to edge insertions and deletions. Recently, Assadi, Onak, Schieber and Solomon (ST…
Round Compression for Parallel Graph Algorithms in Strongly Sublinear Space
Krzysztof Onak
The Massive Parallel Computation (MPC) model is a theoretical framework for popular parallel and distributed platforms such as MapReduce, Hadoop, or Spark. We consider the task of…