- CSB - MetaPress - Google - Bing - Yahoo
 | 2013 | |
|---|---|---|
| i12 |      | Venkatesan Guruswami, Krzysztof Onak: Superlinear lower bounds for multipass graph processing. Electronic Colloquium on Computational Complexity (ECCC) 20: 2 (2013) |
| 2012 | ||
| j1 | | Alexandr Andoni, Krzysztof Onak: Approximating Edit Distance in Near-Linear Time. SIAM J. Comput. 41(6): 1635-1648 (2012) |
| c22 | | Krzysztof Onak, Dana Ron, Michal Rosen, Ronitt Rubinfeld: A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size. SODA 2012: 1123-1131 |
| i11 | | Venkatesan Guruswami, Krzysztof Onak: Superlinear lower bounds for multipass graph processing. CoRR abs/1212.6925 (2012) |
| 2011 | ||
| c21 | | Alan Edelman, Avinatan Hassidim, Huy N. Nguyen, Krzysztof Onak: An Efficient Partitioning Oracle for Bounded-Treewidth Graphs. APPROX-RANDOM 2011: 530-541 |
| c20 | | Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak: Streaming Algorithms via Precision Sampling. FOCS 2011: 363-372 |
| c19 | | Artur Czumaj, Morteza Monemizadeh, Krzysztof Onak, Christian Sohler: Planar Graphs: Random Walks and Bipartiteness Testing. FOCS 2011: 423-432 |
| i10 | | Alan Edelman, Avinatan Hassidim, Huy N. Nguyen, Krzysztof Onak: An Efficient Partitioning Oracle for Bounded-Treewidth Graphs. CoRR abs/1106.4587 (2011) |
| i9 | | Alexandr Andoni, Krzysztof Onak: Approximating Edit Distance in Near-Linear Time. CoRR abs/1109.5635 (2011) |
| i8 | | Krzysztof Onak, Dana Ron, Michal Rosen, Ronitt Rubinfeld: A Near-Optimal Sublinear-Time Algorithm for Approximating the Minimum Vertex Cover Size. CoRR abs/1110.1079 (2011) |
| 2010 | ||
| c18 | | Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak: Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity. FOCS 2010: 377-386 |
| c17 | | |
| c16 | | Alexandr Andoni, Piotr Indyk, Krzysztof Onak, Ronitt Rubinfeld: Sublinear Algorithms in the External Memory Model. Property Testing 2010: 240-243 |
| c15 | | Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak: Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity. Property Testing 2010: 244-252 |
| c14 | | Krzysztof Onak, Ronitt Rubinfeld: Dynamic Approximate Vertex Cover and Maximum Matching. Property Testing 2010: 341-345 |
| c13 | | Krzysztof Onak, Ronitt Rubinfeld: Maintaining a large matching and a small vertex cover. STOC 2010: 457-464 |
| i7 | | Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak: Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity. CoRR abs/1005.4033 (2010) |
| i6 | | Mark de Berg, Krzysztof Onak, Anastasios Sidiropoulos: Fat Polygonal Partitions with Applications to Visualization and Embeddings. CoRR abs/1009.1866 (2010) |
| i5 | | Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak: Streaming Algorithms from Precision Sampling. CoRR abs/1011.1263 (2010) |
| 2009 | ||
| c12 | | |
| c11 | | Avinatan Hassidim, Jonathan A. Kelner, Huy N. Nguyen, Krzysztof Onak: Local Graph Partitions for Approximation and Testing. FOCS 2009: 22-31 |
| c10 | | Alexandr Andoni, Piotr Indyk, Krzysztof Onak, Ronitt Rubinfeld: External Sampling. ICALP (1) 2009: 83-94 |
| c9 | | Alexandr Andoni, Krzysztof Onak: Approximating edit distance in near-linear time. STOC 2009: 199-204 |
| i4 | | |
| 2008 | ||
| c8 | | Krzysztof Onak, Anastasios Sidiropoulos: Circular partitions with applications to visualization and embeddings. Symposium on Computational Geometry 2008: 28-37 |
| c7 | | Huy N. Nguyen, Krzysztof Onak: Constant-Time Approximation Algorithms via Local Improvements. FOCS 2008: 327-336 |
| c6 | | Nicholas J. A. Harvey, Jelani Nelson, Krzysztof Onak: Sketching and Streaming Entropy via Approximation Theory. FOCS 2008: 489-498 |
| c5 | | |
| c4 | | Shay Mozes, Krzysztof Onak, Oren Weimann: Finding an optimal tree searching strategy in linear time. SODA 2008: 1096-1105 |
| i3 | | Nicholas J. A. Harvey, Jelani Nelson, Krzysztof Onak: Sketching and Streaming Entropy via Approximation Theory. CoRR abs/0804.4138 (2008) |
| i2 | | Alexandr Andoni, Andrew McGregor, Krzysztof Onak, Rina Panigrahy: Better Bounds for Frequency Moments in Random-Order Streams. CoRR abs/0808.2222 (2008) |
| 2007 | ||
| c3 | | Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Servedio, Andrew Wan: Testing for Concise Representations. FOCS 2007: 549-558 |
| c2 | | David R. Karger, Krzysztof Onak: Polynomial approximation schemes for smoothed and random instances of multidimensional packing problems. SODA 2007: 1207-1216 |
| i1 | | Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Servedio, Andrew Wan: Testing for Concise Representations. Electronic Colloquium on Computational Complexity (ECCC) 14(077) (2007) |
| 2006 | ||
| c1 | | Krzysztof Onak, Pawel Parys: Generalization of Binary Search: Searching in Trees and Forest-Like Partial Orders. FOCS 2006: 379-388 |
Colors in the list of coauthors
Last update Tue May 21 13:49:01 2013 CET by the DBLP Team —
Data released under the ODC-BY 1.0 license — See also our legal information page