Krzysztof Onak

77 papers A* 26A 4B 1Journal 34Unranked 7

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