Generalization of Binary Search: Searching in Trees and Forest-Like Partial Orders. - Krzysztof Onak; Pawel Parys (FOCS, 2006)

Polynomial approximation schemes for smoothed and random instances of multidimensional packing problems. - David R. Karger; Krzysztof Onak (SODA, 2007)

Testing for Concise Representations. - Ilias Diakonikolas; Homin K. Lee; Kevin Matulef; Krzysztof Onak; Ronitt Rubinfeld; Rocco A. Servedio; Andrew Wan (Electron. Colloquium Comput. Complex., 2007)

Circular partitions with applications to visualization and embeddings. - Krzysztof Onak; Anastasios Sidiropoulos (SCG, 2008)

Sketching and Streaming Entropy via Approximation Theory. - Nicholas J. A. Harvey; Jelani Nelson; Krzysztof Onak (FOCS, 2008)

Constant-Time Approximation Algorithms via Local Improvements. - Huy N. Nguyen; Krzysztof Onak (FOCS, 2008)

Testing Properties of Sets of Points in Metric Spaces. - Krzysztof Onak (ICALP (1), 2008)

Streaming algorithms for estimating entropy. - Nicholas J. A. Harvey; Jelani Nelson; Krzysztof Onak (ITW, 2008)

Finding an optimal tree searching strategy in linear time. - Shay Mozes; Krzysztof Onak; Oren Weimann (SODA, 2008)

Better Bounds for Frequency Moments in Random-Order Streams - Alexandr Andoni; Andrew McGregor 001; Krzysztof Onak; Rina Panigrahy (CoRR, 2008)

The Oil Searching Problem. - Andrew McGregor 001; Krzysztof Onak; Rina Panigrahy (ESA, 2009)

Local Graph Partitions for Approximation and Testing. - Avinatan Hassidim; Jonathan A. Kelner; Huy N. Nguyen; Krzysztof Onak (FOCS, 2009)

External Sampling. - Alexandr Andoni; Piotr Indyk; Krzysztof Onak; Ronitt Rubinfeld (ICALP (1), 2009)

Testing Distribution Identity Efficiently - Krzysztof Onak (CoRR, 2009)

Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity. - Alexandr Andoni; Robert Krauthgamer; Krzysztof Onak (FOCS, 2010)

Sublinear Algorithms in the External Memory Model. - Alexandr Andoni; Piotr Indyk; Krzysztof Onak; Ronitt Rubinfeld (Property Testing, 2010)

Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity. - Alexandr Andoni; Robert Krauthgamer; Krzysztof Onak (Property Testing, 2010)

Sublinear Graph Approximation Algorithms. - Krzysztof Onak (Property Testing, 2010)

Dynamic Approximate Vertex Cover and Maximum Matching. - Krzysztof Onak; Ronitt Rubinfeld (Property Testing, 2010)

Maintaining a large matching and a small vertex cover. - Krzysztof Onak; Ronitt Rubinfeld (STOC, 2010)

Streaming Algorithms from Precision Sampling - Alexandr Andoni; Robert Krauthgamer; Krzysztof Onak (CoRR, 2010)

New sublinear methods in the struggle against classical problems. - Krzysztof Onak (2010)

An Efficient Partitioning Oracle for Bounded-Treewidth Graphs. - Alan Edelman; Avinatan Hassidim; Huy N. Nguyen; Krzysztof Onak (APPROX-RANDOM, 2011)

Streaming Algorithms via Precision Sampling. - Alexandr Andoni; Robert Krauthgamer; Krzysztof Onak (FOCS, 2011)

A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size. - Krzysztof Onak; Dana Ron; Michal Rosen; Ronitt Rubinfeld (SODA, 2012)

Approximating Edit Distance in Near-Linear Time. - Alexandr Andoni; Krzysztof Onak (SIAM J. Comput., 2012)

Superlinear lower bounds for multipass graph processing. - Venkatesan Guruswami; Krzysztof Onak (Electron. Colloquium Comput. Complex., 2013)

Fat Polygonal Partitions with Applications to Visualization and Embeddings. - Mark de Berg; Krzysztof Onak; Anastasios Sidiropoulos (J. Comput. Geom., 2013)

Parallel algorithms for geometric graph problems. - Alexandr Andoni; Aleksandar Nikolov; Krzysztof Onak; Grigory Yaroslavtsev (STOC, 2014)

Fast Algorithms for Parsing Sequences of Parentheses with Few Errors. - Arturs Backurs; Krzysztof Onak (PODS, 2016)

Communication-Efficient Distributed Learning of Discrete Distributions. - Ilias Diakonikolas; Elena Grigorescu; Jerry Li 001; Abhiram Natarajan; Krzysztof Onak; Ludwig Schmidt (NIPS, 2017)

Probability-Revealing Samples. - Krzysztof Onak; Xiaorui Sun (AISTATS, 2018)

Fully dynamic maximal independent set with sublinear update time. - Sepehr Assadi; Krzysztof Onak; Baruch Schieber; Shay Solomon (STOC, 2018)

The query complexity of graph isomorphism: bypassing distribution testing lower bounds. - Krzysztof Onak; Xiaorui Sun (STOC, 2018)

Round Compression for Parallel Graph Algorithms in Strongly Sublinear Space. - Krzysztof Onak (CoRR, 2018)

Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond. - Hossein Esfandiari; MohammadTaghi Hajiaghayi; Vahid Liaghat; Morteza Monemizadeh; Krzysztof Onak (ACM Trans. Algorithms, 2018)

Scalable Fair Clustering. - Arturs Backurs; Piotr Indyk; Krzysztof Onak; Baruch Schieber; Ali Vakilian; Tal Wagner (ICML, 2019)

Fully Dynamic Maximal Independent Set with Sublinear in n Update Time. - Sepehr Assadi; Krzysztof Onak; Baruch Schieber; Shay Solomon (SODA, 2019)

Planar graphs: Random walks and bipartiteness testing. - Artur Czumaj; Morteza Monemizadeh; Krzysztof Onak; Christian Sohler (Random Struct. Algorithms, 2019)

Walking randomly, massively, and efficiently. - Jakub Lacki; Slobodan Mitrovic; Krzysztof Onak; Piotr Sankowski (STOC, 2020)

Round Compression for Parallel Matching Algorithms. - Artur Czumaj; Jakub Lacki; Aleksander Madry; Slobodan Mitrovic; Krzysztof Onak; Piotr Sankowski (SIAM J. Comput., 2020)

Fully Dynamic MIS in Uniformly Sparse Graphs. - Krzysztof Onak; Baruch Schieber; Shay Solomon; Nicole Wein (ACM Trans. Algorithms, 2020)

Dynamic Graph Algorithms with Batch Updates in the Massively Parallel Computation Model. - Krzysztof Nowicki 002; Krzysztof Onak (SODA, 2021)

Adversarially Robust Streaming via Dense-Sparse Trade-offs. - Omri Ben-Eliezer; Talya Eden; Krzysztof Onak (SOSA, 2022)

Dynamic PageRank: Algorithms and Lower Bounds. - Rajesh Jayaram; Jakub Lacki; Slobodan Mitrovic; Krzysztof Onak; Piotr Sankowski (ICALP, 2024)

Compression Barriers in Autoregressive Transformers. - Themistoklis Haris; Krzysztof Onak (COLT, 2025)