Krzysztof Onak's Publications

Random Paper   DBLP

• A Near-Optimal Sublinear-Time Algorithm for Approximating the Minimum Vertex Cover Size (with Dana Ron, Michal Rosen, Ronitt Rubinfeld)
  Accepted to 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)
  Accepted to the 52nd Annual Symposium on Foundations of Computer Science (FOCS 2011).
• Streaming Algorithms via Precision Sampling (with Alexandr Andoni, Robert Krauthgamer)
  Accepted to 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)
  To appear in the special issue of SICOMP on STOC 2009.
  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)
  Full version submitted to a journal.
  
  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