Krzysztof Onak's Publications

Random paper   DBLP

• The Query Complexity of Edit Distance (with Alexandr Andoni, Robert Krauthgamer)
  Manuscript.
• Maintaining a Large Matching or a Small Vertex Cover (with Ronitt Rubinfeld)
  Manuscript.
• 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)
  The 41st ACM Symposium on Theory of Computing (STOC 2009).
  Invited to the special issue of SICOMP on 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).
• 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).