Krzysztof Onak

According to our database, Krzysztof Onak authored at least 45 papers between 2006 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Dynamic PageRank: Algorithms and Lower Bounds.

Rajesh Jayaram, Jakub Lacki, Slobodan Mitrovic, Krzysztof Onak, Piotr Sankowski

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

2022

Adversarially Robust Streaming via Dense-Sparse Trade-offs.

Omri Ben-Eliezer, Talya Eden, Krzysztof Onak

Proceedings of the 5th Symposium on Simplicity in Algorithms, 2022

2021

Dynamic Graph Algorithms with Batch Updates in the Massively Parallel Computation Model.

Krzysztof Nowicki, Krzysztof Onak

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

2020

Fully Dynamic MIS in Uniformly Sparse Graphs.

Krzysztof Onak, Baruch Schieber, Shay Solomon, Nicole Wein

ACM Trans. Algorithms, 2020

Round Compression for Parallel Matching Algorithms.

Artur Czumaj, Jakub Lacki, Aleksander Madry, Slobodan Mitrovic, Krzysztof Onak, Piotr Sankowski

SIAM J. Comput., 2020

Walking randomly, massively, and efficiently.

Jakub Lacki, Slobodan Mitrovic, Krzysztof Onak, Piotr Sankowski

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

2019

Planar graphs: Random walks and bipartiteness testing.

Artur Czumaj, Morteza Monemizadeh, Krzysztof Onak, Christian Sohler

Random Struct. Algorithms, 2019

Fully Dynamic Maximal Independent Set with Sublinear in n Update Time.

Sepehr Assadi, Krzysztof Onak, Baruch Schieber, Shay Solomon

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Scalable Fair Clustering.

Arturs Backurs, Piotr Indyk, Krzysztof Onak, Baruch Schieber, Ali Vakilian, Tal Wagner

Proceedings of the 36th International Conference on Machine Learning, 2019

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

Round Compression for Parallel Graph Algorithms in Strongly Sublinear Space.

Krzysztof Onak

CoRR, 2018

The query complexity of graph isomorphism: bypassing distribution testing lower bounds.

Krzysztof Onak, Xiaorui Sun

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Fully dynamic maximal independent set with sublinear update time.

Sepehr Assadi, Krzysztof Onak, Baruch Schieber, Shay Solomon

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Probability-Revealing Samples.

Krzysztof Onak, Xiaorui Sun

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2018

2017

Communication-Efficient Distributed Learning of Discrete Distributions.

Ilias Diakonikolas, Elena Grigorescu, Jerry Li, Abhiram Natarajan, Krzysztof Onak, Ludwig Schmidt

Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

2016

Fast Algorithms for Parsing Sequences of Parentheses with Few Errors.

Arturs Backurs, Krzysztof Onak

Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2016

2014

Parallel algorithms for geometric graph problems.

Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, Grigory Yaroslavtsev

Proceedings of the Symposium on Theory of Computing, 2014

2013

Fat Polygonal Partitions with Applications to Visualization and Embeddings.

Mark de Berg, Krzysztof Onak, Anastasios Sidiropoulos

J. Comput. Geom., 2013

Superlinear lower bounds for multipass graph processing.

Venkatesan Guruswami, Krzysztof Onak

Electron. Colloquium Comput. Complex., 2013

2012

Approximating Edit Distance in Near-Linear Time.

Alexandr Andoni, Krzysztof Onak

SIAM J. Comput., 2012

A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size.

Krzysztof Onak, Dana Ron, Michal Rosen, Ronitt Rubinfeld

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

2011

Streaming Algorithms via Precision Sampling.

Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

An Efficient Partitioning Oracle for Bounded-Treewidth Graphs.

Alan Edelman, Avinatan Hassidim, Huy N. Nguyen, Krzysztof Onak

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

New sublinear methods in the struggle against classical problems.

Krzysztof Onak

PhD thesis, 2010

Streaming Algorithms from Precision Sampling

Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak

CoRR, 2010

Maintaining a large matching and a small vertex cover.

Krzysztof Onak, Ronitt Rubinfeld

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Dynamic Approximate Vertex Cover and Maximum Matching.

Krzysztof Onak, Ronitt Rubinfeld

Proceedings of the Property Testing - Current Research and Surveys, 2010

Sublinear Graph Approximation Algorithms.

Krzysztof Onak

Proceedings of the Property Testing - Current Research and Surveys, 2010

Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity.

Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak

Proceedings of the Property Testing - Current Research and Surveys, 2010

Sublinear Algorithms in the External Memory Model.

Alexandr Andoni, Piotr Indyk, Krzysztof Onak, Ronitt Rubinfeld

Proceedings of the Property Testing - Current Research and Surveys, 2010

Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity.

Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009

Testing Distribution Identity Efficiently

Krzysztof Onak

CoRR, 2009

External Sampling.

Alexandr Andoni, Piotr Indyk, Krzysztof Onak, Ronitt Rubinfeld

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

Local Graph Partitions for Approximation and Testing.

Avinatan Hassidim, Jonathan A. Kelner, Huy N. Nguyen, Krzysztof Onak

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

The Oil Searching Problem.

Andrew McGregor, Krzysztof Onak, Rina Panigrahy

Proceedings of the Algorithms, 2009

2008

Better Bounds for Frequency Moments in Random-Order Streams

Alexandr Andoni, Andrew McGregor, Krzysztof Onak, Rina Panigrahy

CoRR, 2008

Finding an optimal tree searching strategy in linear time.

Shay Mozes, Krzysztof Onak, Oren Weimann

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Streaming algorithms for estimating entropy.

Nicholas J. A. Harvey, Jelani Nelson, Krzysztof Onak

Proceedings of the 2008 IEEE Information Theory Workshop, 2008

Testing Properties of Sets of Points in Metric Spaces.

Krzysztof Onak

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

Constant-Time Approximation Algorithms via Local Improvements.

Huy N. Nguyen, Krzysztof Onak

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Sketching and Streaming Entropy via Approximation Theory.

Nicholas J. A. Harvey, Jelani Nelson, Krzysztof Onak

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Circular partitions with applications to visualization and embeddings.

Krzysztof Onak, Anastasios Sidiropoulos

Proceedings of the 24th ACM Symposium on Computational Geometry, 2008

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

Polynomial approximation schemes for smoothed and random instances of multidimensional packing problems.

David R. Karger, Krzysztof Onak

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

2006

Generalization of Binary Search: Searching in Trees and Forest-Like Partial Orders.

Krzysztof Onak, Pawel Parys

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006