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).