| 2025 | COLT | Compression Barriers in Autoregressive Transformers. | Themistoklis Haris, Krzysztof Onak |
| 2025 | KDD | The Adaptive Use of Count-Min Sketch: What is Safe and What is Not? | Dragos-Florian Ristache, Krzysztof Onak |
| 2024 | ICALP | Dynamic PageRank: Algorithms and Lower Bounds. | Rajesh Jayaram, Jakub Lacki, Slobodan Mitrovic, Krzysztof Onak, Piotr Sankowski |
| 2021 | SODA | Dynamic Graph Algorithms with Batch Updates in the Massively Parallel Computation Model. | Krzysztof Nowicki, Krzysztof Onak |
| 2020 | STOC | Walking randomly, massively, and efficiently. | Jakub Lacki, Slobodan Mitrovic, Krzysztof Onak, Piotr Sankowski |
| 2019 | ICML | Scalable Fair Clustering. | Arturs Backurs, Piotr Indyk, Krzysztof Onak, Baruch Schieber, Ali Vakilian, Tal Wagner |
| 2019 | SODA | Fully Dynamic Maximal Independent Set with Sublinear in n Update Time. | Sepehr Assadi, Krzysztof Onak, Baruch Schieber, Shay Solomon |
| 2018 | AISTATS | Probability-Revealing Samples. | Krzysztof Onak, Xiaorui Sun |
| 2018 | ICALP | Fully Dynamic MIS in Uniformly Sparse Graphs. | Krzysztof Onak, Baruch Schieber, Shay Solomon, Nicole Wein |
| 2018 | STOC | Fully dynamic maximal independent set with sublinear update time. | Sepehr Assadi, Krzysztof Onak, Baruch Schieber, Shay Solomon |
| 2018 | STOC | Round compression for parallel matching algorithms. | Artur Czumaj, Jakub Lacki, Aleksander Madry, Slobodan Mitrovic, Krzysztof Onak, Piotr Sankowski |
| 2018 | STOC | The query complexity of graph isomorphism: bypassing distribution testing lower bounds. | Krzysztof Onak, Xiaorui Sun |
| 2016 | PODS | Fast Algorithms for Parsing Sequences of Parentheses with Few Errors. | Arturs Backurs, Krzysztof Onak |
| 2015 | SODA | Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond. | Hossein Esfandiari, Mohammad Taghi Hajiaghayi, Vahid Liaghat, Morteza Monemizadeh, Krzysztof Onak |
| 2014 | STOC | Parallel algorithms for geometric graph problems. | Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, Grigory Yaroslavtsev |
| 2012 | SODA | A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size. | Krzysztof Onak, Dana Ron, Michal Rosen, Ronitt Rubinfeld |
| 2011 | FOCS | Streaming Algorithms via Precision Sampling. | Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak |
| 2011 | FOCS | Planar Graphs: Random Walks and Bipartiteness Testing. | Artur Czumaj, Morteza Monemizadeh, Krzysztof Onak, Christian Sohler |
| 2010 | FOCS | Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity. | Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak |
| 2010 | STOC | Maintaining a large matching and a small vertex cover. | Krzysztof Onak, Ronitt Rubinfeld |
| 2009 | ESA | The Oil Searching Problem. | Andrew McGregor, Krzysztof Onak, Rina Panigrahy |
| 2009 | FOCS | Local Graph Partitions for Approximation and Testing. | Avinatan Hassidim, Jonathan A. Kelner, Huy N. Nguyen, Krzysztof Onak |
| 2009 | ICALP | External Sampling. | Alexandr Andoni, Piotr Indyk, Krzysztof Onak, Ronitt Rubinfeld |
| 2009 | STOC | Approximating edit distance in near-linear time. | Alexandr Andoni, Krzysztof Onak |
| 2008 | FOCS | Sketching and Streaming Entropy via Approximation Theory. | Nicholas J. A. Harvey, Jelani Nelson, Krzysztof Onak |
| 2008 | FOCS | Constant-Time Approximation Algorithms via Local Improvements. | Huy N. Nguyen, Krzysztof Onak |
| 2008 | ICALP | Testing Properties of Sets of Points in Metric Spaces. | Krzysztof Onak |
| 2008 | ITW | Streaming algorithms for estimating entropy. | Nicholas J. A. Harvey, Jelani Nelson, Krzysztof Onak |
| 2008 | SODA | Finding an optimal tree searching strategy in linear time. | Shay Mozes, Krzysztof Onak, Oren Weimann |
| 2007 | FOCS | Testing for Concise Representations. | Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Servedio, Andrew Wan |
| 2007 | SODA | Polynomial approximation schemes for smoothed and random instances of multidimensional packing problems. | David R. Karger, Krzysztof Onak |
| 2006 | FOCS | Generalization of Binary Search: Searching in Trees and Forest-Like Partial Orders. | Krzysztof Onak, Pawel Parys |