Krzysztof Onak's Publications

DBLP   Google Scholar

• Walking Randomly, Massively, and Efficiently (with Jakub Łącki, Slobodan Mitrović, Piotr Sankowski)
  The 52nd ACM Symposium on Theory of Computing (STOC 2020).
• Scalable Fair Clustering (with Arturs Backurs, Piotr Indyk, Baruch Schieber, Ali Vakilian, Tal Wagner)
  The 36th International Conference on Machine Learning (ICML 2019).
• Fully Dynamic Maximal Independent Set with Sublinear in $n$ Update Time (with Sepehr Assadi, Baruch Schieber, Shay Solomon)
  The 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019).
• Round Compression for Parallel Graph Algorithms in Strongly Sublinear Space
  Manuscript on arXiv, 2018.
• Fully Dynamic MIS in Uniformly Sparse Graphs (with Baruch Schieber, Shay Solomon, Nicole Wein)
  The 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018).
• Round Compression for Parallel Matching Algorithms (with Artur Czumaj, Jakub Łącki, Aleksander Mądry, Slobodan Mitrović, Piotr Sankowski)
  The 50th ACM Symposium on Theory of Computing (STOC 2018).
  Accepted to the special issue of SICOMP on STOC 2018.
• Fully Dynamic Maximal Independent Set with Sublinear Update Time (with Sepehr Assadi, Baruch Schieber, Shay Solomon)
  The 50th ACM Symposium on Theory of Computing (STOC 2018).
• The Query Complexity of Graph Isomorphism: Bypassing Distribution Testing Lower Bounds (with Xiaorui Sun)
  The 50th ACM Symposium on Theory of Computing (STOC 2018).
• Probability-Revealing Samples (with Xiaorui Sun)
  The 21st International Conference on Artificial Intelligence and Statistics (AISTATS 2018).
• Communication-Efficient Distributed Learning of Discrete Distributions (with Ilias Diakonikolas, Elena Grigorescu, Jerry Li, Abhiram Natarajan, Ludwig Schmidt)
  The 31 Annual Conference on Neural Information Processing Systems (NIPS 2017).
  Oral presentation.
• Fast Algorithms for Parsing Sequences of Parentheses with Few Errors (with Arturs Backurs)
  The 35th ACM Symposium on Principles of Database Systems (PODS 2016).
• Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond (with Hossein Esfandiari, Mohammad T Hajiaghayi, Vahid Liaghat, Morteza Monemizadeh)
  The 26rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015).
  ACM Transactions on Algorithms 14(4), 2018.
• Parallel Algorithms for Geometric Graph Problems (with Alexandr Andoni, Aleksandar Nikolov, Grigory Yaroslavtsev)
  The 46th ACM Symposium on Theory of Computing (STOC 2014).
• Superlinear Lower Bounds for Multipass Graph Processing (with Venkatesan Guruswami)
  The 28th IEEE Conference on Computational Complexity (CCC 2013).
  Invited to a special issue of Algorithmica on Information Complexity and Applications: Algorithmica 76(3), 2016.
• On the Complexity of Learning and Testing Hyperfinite Graphs
• A Near-Optimal Sublinear-Time Algorithm for Approximating the Minimum Vertex Cover Size (with Dana Ron, Michal Rosen, Ronitt Rubinfeld)
  The 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012).
• Planar Graphs: Random Walks and Bipartiteness Testing (with Artur Czumaj, Morteza Monemizadeh, Christian Sohler)
  The 52nd Annual Symposium on Foundations of Computer Science (FOCS 2011).
  Random Structures & Algorithms 55(1), 2019.
• Streaming Algorithms via Precision Sampling (with Alexandr Andoni, Robert Krauthgamer)
  The 52nd Annual Symposium on Foundations of Computer Science (FOCS 2011).
• An Efficient Partitioning Oracle for Bounded-Treewidth Graphs (with Alan Edelman, Avinatan Hassidim, Huy N. Nguyen)
  The 15th International Workshop on Randomization and Computation (RANDOM 2011)
• New Sublinear Methods in the Struggle Against Classical Problems
  PhD Thesis, Massachusetts Institute of Technology, September 2010.
• Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity (with Alexandr Andoni, Robert Krauthgamer)
  The 51st Annual Symposium on Foundations of Computer Science (FOCS 2010).
• Maintaining a Large Matching and a Small Vertex Cover (with Ronitt Rubinfeld)
  The 42nd ACM Symposium on Theory of Computing (STOC 2010).
  
• Local Graph Partitions for Approximation and Testing (with Avinatan Hassidim, Jonathan A. Kelner, Huy N. Nguyen)
  The 50th Annual Symposium on Foundations of Computer Science (FOCS 2009).
• Testing Distribution Identity Efficiently
  Short note on arXiv, Nov 2009.
• The Oil Searching Problem (with Andrew McGregor, Rina Panigrahy)
  The 17th Annual European Symposium on Algorithms (ESA 2009).
• External Sampling (with Alexandr Andoni, Piotr Indyk, Ronitt Rubinfeld)
  The 36th International Colloquium on Automata, Languages and Programming (ICALP 2009).
• Approximating Edit Distance in Near-Linear Time (with Alexandr Andoni)
  SIAM Journal on Computing, 41(6), 2012 (special issue on STOC 2009).
  Preliminary version in the 41st ACM Symposium on Theory of Computing (STOC 2009).
• Constant-Time Approximation Algorithms via Local Improvements (with Huy N. Nguyen)
  The 49th Annual Symposium on Foundations of Computer Science (FOCS 2008).
• Sketching and Streaming Entropy via Approximation Theory (with Nicholas J. A. Harvey, Jelani Nelson)
  The 49th Annual Symposium on Foundations of Computer Science (FOCS 2008).
• Better Bounds for Frequency Moments in Random-Order Streams (with Alexandr Andoni, Andrew McGregor, Rina Panigrahy)
  Short note on arXiv, Aug 2008.
• Testing Properties of Sets of Points in Metric Spaces
  The 35th International Colloquium on Automata, Languages and Programming (ICALP 2008).
• Fat Polygonal Partitions with Applications to Visualization and Embeddings (with Mark de Berg, Anastasios Sidiropoulos)
  Journal of Computational Geometry, 4(1), 2013.
  
  Preliminary version:
  Circular Partitions with Applications to Visualization and Embeddings (with Anastasios Sidiropoulos)
  The 24th Annual ACM Symposium on Computational Geometry (SoCG 2008).
• Finding an Optimal Tree Searching Strategy in Linear Time (with Shay Mozes, Oren Weimann)
  The 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008).
• Testing for Concise Representations (with Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Ronitt Rubinfeld, Rocco A. Servedio, Andrew Wan)
  The 48th Annual Symposium on Foundations of Computer Science (FOCS 2007).
• Polynomial Approximation Schemes for Smoothed And Random Instances of Multidimensional Packing Problems (with David Karger)
  The 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007).
• Generalization of Binary Search: Searching in Trees and Forest-Like Partial Orders (with Paweł Parys)
  The 47th Annual Symposium on Foundations of Computer Science (FOCS 2006).

Other:

• Open Problems in Data Streams, Property Testing, and Related Topics (edited with Piotr Indyk, Andrew McGregor, Ilan Newman)
  June 2011