Krzysztof Onak

ORCID

Publication Activity (10 Years)

Years Active: 2006-2024
Publications (10 Years): 28

Top Venues

Massachusetts Institute of Technology, Cambridge, MA, USA (PHD)

Education History

Massachusetts Institute of Technology, Cambridge, MA, USA

PHD

Publications

Rajesh Jayaram, Jakub Lacki, Slobodan Mitrovic, Krzysztof Onak, Piotr Sankowski
Dynamic PageRank: Algorithms and Lower Bounds. CoRR (2024)
Rajesh Jayaram, Jakub Lacki, Slobodan Mitrovic, Krzysztof Onak, Piotr Sankowski
Dynamic PageRank: Algorithms and Lower Bounds. ICALP (2024)
Omri Ben-Eliezer, Talya Eden, Krzysztof Onak
Adversarially Robust Streaming via Dense-Sparse Trade-offs. SOSA (2022)
Krzysztof Nowicki, Krzysztof Onak
Dynamic Graph Algorithms with Batch Updates in the Massively Parallel Computation Model. SODA (2021)
Omri Ben-Eliezer, Talya Eden, Krzysztof Onak
Adversarially Robust Streaming via Dense-Sparse Trade-offs. CoRR (2021)
Krzysztof Onak, Baruch Schieber, Shay Solomon, Nicole Wein
Fully Dynamic MIS in Uniformly Sparse Graphs. ACM Trans. Algorithms 16 (2) (2020)
Artur Czumaj, Jakub Lacki, Aleksander Madry, Slobodan Mitrovic, Krzysztof Onak, Piotr Sankowski
Round Compression for Parallel Matching Algorithms. SIAM J. Comput. 49 (5) (2020)
Krzysztof Nowicki, Krzysztof Onak
Dynamic Graph Algorithms with Batch Updates in the Massively Parallel Computation Model. CoRR (2020)
Jakub Lacki, Slobodan Mitrovic, Krzysztof Onak, Piotr Sankowski
Walking randomly, massively, and efficiently. STOC (2020)
Artur Czumaj, Morteza Monemizadeh, Krzysztof Onak, Christian Sohler
Planar graphs: Random walks and bipartiteness testing. Random Struct. Algorithms 55 (1) (2019)
Arturs Backurs, Piotr Indyk, Krzysztof Onak, Baruch Schieber, Ali Vakilian, Tal Wagner
Scalable Fair Clustering. CoRR (2019)
Arturs Backurs, Piotr Indyk, Krzysztof Onak, Baruch Schieber, Ali Vakilian, Tal Wagner
Scalable Fair Clustering. ICML (2019)
Jakub Lacki, Slobodan Mitrovic, Krzysztof Onak, Piotr Sankowski
Walking Randomly, Massively, and Efficiently. CoRR (2019)
Sepehr Assadi, Krzysztof Onak, Baruch Schieber, Shay Solomon
Fully Dynamic Maximal Independent Set with Sublinear in n Update Time. SODA (2019)
Sepehr Assadi, Krzysztof Onak, Baruch Schieber, Shay Solomon
Fully Dynamic Maximal Independent Set with Sublinear in n Update Time. CoRR (2018)
Krzysztof Onak, Baruch Schieber, Shay Solomon, Nicole Wein
Fully Dynamic MIS in Uniformly Sparse Graphs. CoRR (2018)
Sepehr Assadi, Krzysztof Onak, Baruch Schieber, Shay Solomon
Fully Dynamic Maximal Independent Set with Sublinear Update Time. CoRR (2018)
Hossein Esfandiari, MohammadTaghi Hajiaghayi, Vahid Liaghat, Morteza Monemizadeh, Krzysztof Onak
Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond. ACM Trans. Algorithms 14 (4) (2018)
Krzysztof Onak, Baruch Schieber, Shay Solomon, Nicole Wein
Fully Dynamic MIS in Uniformly Sparse Graphs. ICALP (2018)
Sepehr Assadi, Krzysztof Onak, Baruch Schieber, Shay Solomon
Fully dynamic maximal independent set with sublinear update time. STOC (2018)
Krzysztof Onak, Xiaorui Sun
The query complexity of graph isomorphism: bypassing distribution testing lower bounds. STOC (2018)
Artur Czumaj, Jakub Lacki, Aleksander Madry, Slobodan Mitrovic, Krzysztof Onak, Piotr Sankowski
Round compression for parallel matching algorithms. STOC (2018)
Krzysztof Onak, Xiaorui Sun
Probability-Revealing Samples. AISTATS (2018)
Krzysztof Onak
Round Compression for Parallel Graph Algorithms in Strongly Sublinear Space. CoRR (2018)
Ilias Diakonikolas, Elena Grigorescu, Jerry Li, Abhiram Natarajan, Krzysztof Onak, Ludwig Schmidt
Communication-Efficient Distributed Learning of Discrete Distributions. NIPS (2017)
Artur Czumaj, Jakub Lacki, Aleksander Madry, Slobodan Mitrovic, Krzysztof Onak, Piotr Sankowski
Round Compression for Parallel Matching Algorithms. CoRR (2017)
Arturs Backurs, Krzysztof Onak
Fast Algorithms for Parsing Sequences of Parentheses with Few Errors. PODS (2016)
Venkatesan Guruswami, Krzysztof Onak
Superlinear Lower Bounds for Multipass Graph Processing. Algorithmica 76 (3) (2016)
Hossein Esfandiari, Mohammad Taghi Hajiaghayi, Vahid Liaghat, Morteza Monemizadeh, Krzysztof Onak
Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond. SODA (2015)
Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, Grigory Yaroslavtsev
Parallel Algorithms for Geometric Graph Problems. CoRR (2014)
Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, Grigory Yaroslavtsev
Parallel algorithms for geometric graph problems. STOC (2014)
Artur Czumaj, Morteza Monemizadeh, Krzysztof Onak, Christian Sohler
Planar Graphs: Random Walks and Bipartiteness Testing. CoRR (2014)
Venkatesan Guruswami, Krzysztof Onak
Superlinear Lower Bounds for Multipass Graph Processing. Computational Complexity Conference (2013)
Venkatesan Guruswami, Krzysztof Onak
Superlinear lower bounds for multipass graph processing. Electron. Colloquium Comput. Complex. 20 (2013)
Mark de Berg, Krzysztof Onak, Anastasios Sidiropoulos
Fat Polygonal Partitions with Applications to Visualization and Embeddings. J. Comput. Geom. 4 (1) (2013)
Venkatesan Guruswami, Krzysztof Onak
Superlinear lower bounds for multipass graph processing CoRR (2012)
Krzysztof Onak, Dana Ron, Michal Rosen, Ronitt Rubinfeld
A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size. SODA (2012)
Alexandr Andoni, Krzysztof Onak
Approximating Edit Distance in Near-Linear Time. SIAM J. Comput. 41 (6) (2012)
Alan Edelman, Avinatan Hassidim, Huy N. Nguyen, Krzysztof Onak
An Efficient Partitioning Oracle for Bounded-Treewidth Graphs CoRR (2011)
Alexandr Andoni, Krzysztof Onak
Approximating Edit Distance in Near-Linear Time CoRR (2011)
Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak
Streaming Algorithms via Precision Sampling. FOCS (2011)
Krzysztof Onak, Dana Ron, Michal Rosen, Ronitt Rubinfeld
A Near-Optimal Sublinear-Time Algorithm for Approximating the Minimum Vertex Cover Size CoRR (2011)
Artur Czumaj, Morteza Monemizadeh, Krzysztof Onak, Christian Sohler
Planar Graphs: Random Walks and Bipartiteness Testing. FOCS (2011)
Alan Edelman, Avinatan Hassidim, Huy N. Nguyen, Krzysztof Onak
An Efficient Partitioning Oracle for Bounded-Treewidth Graphs. APPROX-RANDOM (2011)
Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak
Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity CoRR (2010)
Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak
Streaming Algorithms from Precision Sampling CoRR (2010)
Mark de Berg, Krzysztof Onak, Anastasios Sidiropoulos
Fat Polygonal Partitions with Applications to Visualization and Embeddings CoRR (2010)
Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak
Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity. FOCS (2010)
Krzysztof Onak, Ronitt Rubinfeld
Maintaining a large matching and a small vertex cover. STOC (2010)
Krzysztof Onak
Testing Distribution Identity Efficiently CoRR (2009)
Andrew McGregor, Krzysztof Onak, Rina Panigrahy
The Oil Searching Problem. ESA (2009)
Avinatan Hassidim, Jonathan A. Kelner, Huy N. Nguyen, Krzysztof Onak
Local Graph Partitions for Approximation and Testing. FOCS (2009)
Alexandr Andoni, Piotr Indyk, Krzysztof Onak, Ronitt Rubinfeld
External Sampling. ICALP (1) (2009)
Alexandr Andoni, Krzysztof Onak
Approximating edit distance in near-linear time. STOC (2009)
Nicholas J. A. Harvey, Jelani Nelson, Krzysztof Onak
Streaming algorithms for estimating entropy. ITW (2008)
Nicholas J. A. Harvey, Jelani Nelson, Krzysztof Onak
Sketching and Streaming Entropy via Approximation Theory CoRR (2008)
Krzysztof Onak
Testing Properties of Sets of Points in Metric Spaces. ICALP (1) (2008)
Huy N. Nguyen, Krzysztof Onak
Constant-Time Approximation Algorithms via Local Improvements. FOCS (2008)
Alexandr Andoni, Andrew McGregor, Krzysztof Onak, Rina Panigrahy
Better Bounds for Frequency Moments in Random-Order Streams CoRR (2008)
Shay Mozes, Krzysztof Onak, Oren Weimann
Finding an optimal tree searching strategy in linear time. SODA (2008)
Krzysztof Onak, Anastasios Sidiropoulos
Circular partitions with applications to visualization and embeddings. SCG (2008)
Nicholas J. A. Harvey, Jelani Nelson, Krzysztof Onak
Sketching and Streaming Entropy via Approximation Theory. FOCS (2008)
Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Servedio, Andrew Wan
Testing for Concise Representations. FOCS (2007)
David R. Karger, Krzysztof Onak
Polynomial approximation schemes for smoothed and random instances of multidimensional packing problems. SODA (2007)
Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Servedio, Andrew Wan
Testing for Concise Representations. Electron. Colloquium Comput. Complex. 14 (077) (2007)
Krzysztof Onak, Pawel Parys
Generalization of Binary Search: Searching in Trees and Forest-Like Partial Orders. FOCS (2006)

Krzysztof Onak.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Krzysztof Onak