KO
Krzysztof Onak
cs.DScs.DCcs.CCcs.CGcs.LGcs.AI
On Valency
published · living versionsW_gqr7y4r5·v1 · currentpublished
Preprints & journals
24 papers in the corpus · 2008–2026Efficient Algorithms for Adversarially Robust Approximate Nearest Neighbor Search2601.00272v1 · Alexandr Andoni, Themistoklis Haris, Esty Kelman et al.2026 · 0 citationsarXiv
Robust Streaming Against Low-Memory Adversaries2511.01769v1 · Omri Ben-Eliezer, Krzysztof Onak, Sandeep Silwal2025 · 0 citationsarXiv
Compression Barriers for Autoregressive Transformers2502.15955v1 · Themistoklis Haris, Krzysztof Onak2025 · 0 citationsarXiv
Dynamic PageRank: Algorithms and Lower Bounds2404.16267v2 · Rajesh Jayaram, Jakub \Lacki, Slobodan Mitrovi'c et al.2024 · 25 citationsarXiv
Adversarially Robust Streaming via Dense--Sparse Trade-offs2109.03785v1 · Omri Ben-Eliezer, Talya Eden, Krzysztof Onak2021 · 13 citationsarXiv
Dynamic Graph Algorithms with Batch Updates in the Massively Parallel Computation Model2002.07800v2 · Krzysztof Nowicki, Krzysztof Onak2020 · 5 citationsarXiv
Walking Randomly, Massively, and Efficiently1907.05391v4 · Jakub \Lacki, Slobodan Mitrovi'c, Krzysztof Onak et al.2019 · 20 citationsarXiv
Scalable Fair Clustering1902.03519v2 · Arturs Backurs, Piotr Indyk, Krzysztof Onak et al.2019 · 101 citationsarXivon Valency
Fully Dynamic MIS in Uniformly Sparse Graphs1808.10316v1 · Krzysztof Onak, Baruch Schieber, Shay Solomon et al.2018 · 16 citationsarXiv
Round Compression for Parallel Graph Algorithms in Strongly Sublinear Space1807.08745v1 · Krzysztof Onak2018 · 16 citationsarXiv
Fully Dynamic Maximal Independent Set with Sublinear in n Update Time1806.10051v1 · Sepehr Assadi, Krzysztof Onak, Baruch Schieber et al.2018 · 30 citationsarXiv
Fully Dynamic Maximal Independent Set with Sublinear Update Time1802.09709v1 · Sepehr Assadi, Krzysztof Onak, Baruch Schieber et al.2018 · 55 citationsarXiv
Round Compression for Parallel Matching Algorithms1707.03478v2 · Artur Czumaj, Jakub \Lacki, Aleksander Madry et al.2017 · 67 citationsarXiv
Planar Graphs: Random Walks and Bipartiteness Testing1407.2109v4 · Artur Czumaj, Morteza Monemizadeh, Krzysztof Onak et al.2014 · 20 citationsarXiv
Parallel Algorithms for Geometric Graph Problems1401.0042v2 · Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak et al.2013 · 127 citationsarXiv
Superlinear lower bounds for multipass graph processing1212.6925v4 · Venkatesan Guruswami, Krzysztof Onak2012 · 44 citationsarXiv
A Near-Optimal Sublinear-Time Algorithm for Approximating the Minimum Vertex Cover Size1110.1079v1 · Krzysztof Onak, Dana Ron, Michal Rosen et al.2011 · 58 citationsarXiv
Approximating Edit Distance in Near-Linear Time1109.5635v1 · Alexandr Andoni, Krzysztof Onak2011 · 49 citationsarXiv
An Efficient Partitioning Oracle for Bounded-Treewidth Graphs1106.4587v1 · Alan Edelman, Avinatan Hassidim, Huy N. Nguyen et al.2011 · 19 citationsarXiv
Streaming Algorithms from Precision Sampling1011.1263v2 · Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak2010 · 19 citationsarXiv
Fat Polygonal Partitions with Applications to Visualization and Embeddings1009.1866v2 · Mark de Berg, Krzysztof Onak, Anastasios Sidiropoulos2010 · 8 citationsarXiv
Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity1005.4033v1 · Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak2010 · 84 citationsarXiv
Testing Distribution Identity Efficiently0910.3243v1 · Krzysztof Onak2009 · 1 citationarXiv
Sketching and Streaming Entropy via Approximation Theory0804.4138v1 · Nicholas J. A. Harvey, Jelani Nelson, Krzysztof Onak2008 · 88 citationsarXiv
Career total: 77 works. 24 are in this corpus.
Profile built from the corpus for this byline.
Author records are still filling in while the Hub is in alpha. If this is your page, you'll be able to claim it soon. Spot a mistake? Tell us.