Krzysztof Onak

Most-cited papers

Scalable Fair Clustering
A. Backurs, P. Indyk, Krzysztof Onak, B. Schieber +2 more
2019International Conference on Machine Learning237 citations
Semantic Scholar
Constant-Time Approximation Algorithms via Local Improvements
H. N. Nguyen, Krzysztof Onak
20082008 49th Annual IEEE Symposium on Foundations of Computer Science208 citations
Semantic Scholar
Parallel algorithms for geometric graph problems
Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, G. Yaroslavtsev
2013Symposium on the Theory of Computing193 citations
Semantic Scholar
Local Graph Partitions for Approximation and Testing
A. Hassidim, Jonathan A. Kelner, H. N. Nguyen, Krzysztof Onak
20092009 50th Annual IEEE Symposium on Foundations of Computer Science147 citations Open access
Semantic Scholar
Testing for Concise Representations
Ilias Diakonikolas, Ho-Min K. Lee, Kevin Matulef, Krzysztof Onak +3 more
2007IEEE Annual Symposium on Foundations of Computer Science132 citations Open access
Semantic Scholar
Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity
Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak
2010IEEE Annual Symposium on Foundations of Computer Science129 citations
Semantic Scholar
Maintaining a large matching and a small vertex cover
Krzysztof Onak, R. Rubinfeld
2010Symposium on the Theory of Computing125 citations Open access
Semantic Scholar
Approximating edit distance in near-linear time
Alexandr Andoni, Krzysztof Onak
2009Symposium on the Theory of Computing124 citations Open access
Semantic Scholar
Sketching and Streaming Entropy via Approximation Theory
Nicholas J. A. Harvey, Jelani Nelson, Krzysztof Onak
20082008 49th Annual IEEE Symposium on Foundations of Computer Science118 citations Open access
Semantic Scholar
Streaming Algorithms via Precision Sampling
Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak
2010IEEE Annual Symposium on Foundations of Computer Science117 citations
Semantic Scholar
Round compression for parallel matching algorithms
A. Czumaj, J. Lacki, A. Ma̧dry, Slobodan Mitrovic +2 more
2017Symposium on the Theory of Computing106 citations Open access
Semantic Scholar
A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
Krzysztof Onak, D. Ron, M. Rosen, R. Rubinfeld
2011ACM-SIAM Symposium on Discrete Algorithms105 citations
Semantic Scholar
Superlinear Lower Bounds for Multipass Graph Processing
V. Guruswami, Krzysztof Onak
2012Algorithmica94 citations Open access
Semantic Scholar
Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
Hossein Esfandiari, M. Hajiaghayi, Vahid Liaghat, M. Monemizadeh +1 more
2015ACM-SIAM Symposium on Discrete Algorithms89 citations
Semantic Scholar
Fully dynamic maximal independent set with sublinear update time
Sepehr Assadi, Krzysztof Onak, B. Schieber, Shay Solomon
2018Symposium on the Theory of Computing82 citations Open access
Semantic Scholar
Generalization of Binary Search: Searching in Trees and Forest-Like Partial Orders
Krzysztof Onak, P. Parys
2006IEEE Annual Symposium on Foundations of Computer Science81 citations
Semantic Scholar
Finding an optimal tree searching strategy in linear time
S. Mozes, Krzysztof Onak, Oren Weimann
2008ACM-SIAM Symposium on Discrete Algorithms65 citations
Semantic Scholar
Fully Dynamic Maximal Independent Set with Sublinear in n Update Time
Sepehr Assadi, Krzysztof Onak, B. Schieber, Shay Solomon
2018ACM-SIAM Symposium on Discrete Algorithms43 citations
Semantic Scholar
Adversarially Robust Streaming via Dense-Sparse Trade-offs
Omri Ben-Eliezer, T. Eden, Krzysztof Onak
2021SIAM Symposium on Simplicity in Algorithms41 citations Open access
Semantic Scholar
Communication-Efficient Distributed Learning of Discrete Distributions
Ilias Diakonikolas, Elena Grigorescu, Jerry Li, Abhiram Natarajan +2 more
2017Neural Information Processing Systems35 citations
Semantic Scholar
Planar Graphs: Random Walks and Bipartiteness Testing
A. Czumaj, M. Monemizadeh, Krzysztof Onak, C. Sohler
2011IEEE Annual Symposium on Foundations of Computer Science35 citations Open access
Semantic Scholar
Round Compression for Parallel Graph Algorithms in Strongly Sublinear Space
Krzysztof Onak
2018arXiv.org34 citations
Semantic Scholar
Fully Dynamic MIS in Uniformly Sparse Graphs
Krzysztof Onak, B. Schieber, Shay Solomon, Nicole Wein
2018International Colloquium on Automata, Languages and Programming33 citations Open access
Semantic Scholar
Circular partitions with applications to visualization and embeddings
Krzysztof Onak, Anastasios Sidiropoulos
2008SCG '0832 citations
Semantic Scholar
Streaming Algorithms from Precision Sampling
Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak
2010arXiv.org27 citations
Semantic Scholar
Probability-Revealing Samples
Krzysztof Onak, Xiaorui Sun
2018International Conference on Artificial Intelligence and Statistics23 citations
Semantic Scholar
Open Problems in Data Streams, Property Testing, and Related Topics
P. Indyk, A. Mcgregor, Nir Ailon, N. Alon +49 more
201122 citations
Semantic Scholar
Fat Polygonal Partitions with Applications to Visualization and Embeddings
Mark de Berg, Krzysztof Onak, Anastasios Sidiropoulos
2010Journal of Computational Geometry22 citations
Semantic Scholar
An Efficient Partitioning Oracle for Bounded-Treewidth Graphs
A. Edelman, A. Hassidim, H. N. Nguyen, Krzysztof Onak
2011International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques19 citations
Semantic Scholar
Streaming algorithms for estimating entropy
Nicholas J. A. Harvey, Jelani Nelson, Krzysztof Onak
20082008 IEEE Information Theory Workshop18 citations
Semantic Scholar
Polynomial approximation schemes for smoothed and random instances of multidimensional packing problems
David R Karger, Krzysztof Onak
2007ACM-SIAM Symposium on Discrete Algorithms18 citations
Semantic Scholar
New sublinear methods in the struggle against classical problems
Krzysztof Onak
201017 citations
Semantic Scholar
The Oil Searching Problem
A. Mcgregor, Krzysztof Onak, Rina Panigrahy
2009Embedded Systems and Applications17 citations
Semantic Scholar
Better Bounds for Frequency Moments in Random-Order Streams
Alexandr Andoni, A. Mcgregor, Krzysztof Onak, Rina Panigrahy
2008arXiv.org16 citations
Semantic Scholar
Dynamic Graph Algorithms with Batch Updates in the Massively Parallel Computation Model
Krzysztof Nowicki, Krzysztof Onak
2020ACM-SIAM Symposium on Discrete Algorithms15 citations Open access
Semantic Scholar
Fast Algorithms for Parsing Sequences of Parentheses with Few Errors
A. Backurs, Krzysztof Onak
2016ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems13 citations
Semantic Scholar
Testing Properties of Sets of Points in Metric Spaces
Krzysztof Onak
2008International Colloquium on Automata, Languages and Programming7 citations
Semantic Scholar
The query complexity of graph isomorphism: bypassing distribution testing lower bounds
Krzysztof Onak, Xiaorui Sun
2018Symposium on the Theory of Computing6 citations
Semantic Scholar
External Sampling
Alexandr Andoni, P. Indyk, Krzysztof Onak, R. Rubinfeld
2009International Colloquium on Automata, Languages and Programming6 citations
Semantic Scholar
Testing for Concise Representations
Ilias Diakonikolas, Ho-Min K. Lee, K. Matule, Krzysztof Onak +3 more
2007IEEE Annual Symposium on Foundations of Computer Science5 citations
Semantic Scholar
The Adaptive Use of Count-Min Sketch: What is Safe and What is Not?
Dragos Ristache, Krzysztof Onak
2025Knowledge Discovery and Data Mining4 citations Open access
Semantic Scholar
Robust Streaming Against Low-Memory Adversaries
Omri Ben-Eliezer, Krzysztof Onak, Sandeep Silwal
2025Information Technology Convergence and Services3 citations
Semantic Scholar
On the Complexity of Learning and Testing Hyperfinite Graphs
Krzysztof Onak
20123 citations
Semantic Scholar
Dynamic Approximate Vertex Cover and Maximum Matching
Krzysztof Onak, R. Rubinfeld
2010Property Testing2 citations Open access
Semantic Scholar
Sublinear Graph Approximation Algorithms
Krzysztof Onak
2010Property Testing1 citations
Semantic Scholar
Testing Distribution Identity Efficiently
Krzysztof Onak
2009arXiv.org1 citations
Semantic Scholar
N ov 2 01 9 Walking Randomly , Massively , and Efficiently
J. Lacki, Krzysztof Onak, P. Sankowski
20190 citations
Semantic Scholar
Ju l 2 01 7 Round Compression for Parallel Matching Algorithms
A. Czumaj, A. Ma̧dry, Slobodan Mitrovic, Krzysztof Onak
20170 citations
Semantic Scholar
On the Complexity of Learning and Testing Hypernite Graphs
Krzysztof Onak
20120 citations
Semantic Scholar
Sublinear Algorithms in the External Memory Model
Alexandr Andoni, P. Indyk, Krzysztof Onak, R. Rubinfeld
2010Property Testing0 citations Open access
Semantic Scholar