Krzysztof Onak

	2012
32		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
	2011
31		Alan Edelman, Avinatan Hassidim, Huy N. Nguyen, Krzysztof Onak: An Efficient Partitioning Oracle for Bounded-Treewidth Graphs. APPROX-RANDOM 2011: 530-541
30		Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak: Streaming Algorithms via Precision Sampling. FOCS 2011: 363-372
29		Artur Czumaj, Morteza Monemizadeh, Krzysztof Onak, Christian Sohler: Planar Graphs: Random Walks and Bipartiteness Testing. FOCS 2011: 423-432
28		Alan Edelman, Avinatan Hassidim, Huy N. Nguyen, Krzysztof Onak: An Efficient Partitioning Oracle for Bounded-Treewidth Graphs CoRR abs/1106.4587: (2011)
27		Alexandr Andoni, Krzysztof Onak: Approximating Edit Distance in Near-Linear Time CoRR abs/1109.5635: (2011)
26		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
25		Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak: Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity. FOCS 2010: 377-386
24		Krzysztof Onak: Sublinear Graph Approximation Algorithms. Property Testing 2010: 158-166
23		Alexandr Andoni, Piotr Indyk, Krzysztof Onak, Ronitt Rubinfeld: Sublinear Algorithms in the External Memory Model. Property Testing 2010: 240-243
22		Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak: Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity. Property Testing 2010: 244-252
21		Krzysztof Onak, Ronitt Rubinfeld: Dynamic Approximate Vertex Cover and Maximum Matching. Property Testing 2010: 341-345
20		Krzysztof Onak, Ronitt Rubinfeld: Maintaining a large matching and a small vertex cover. STOC 2010: 457-464
19		Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak: Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity CoRR abs/1005.4033: (2010)
18		Mark de Berg, Krzysztof Onak, Anastasios Sidiropoulos: Fat Polygonal Partitions with Applications to Visualization and Embeddings CoRR abs/1009.1866: (2010)
17		Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak: Streaming Algorithms from Precision Sampling CoRR abs/1011.1263: (2010)
	2009
16		Andrew McGregor, Krzysztof Onak, Rina Panigrahy: The Oil Searching Problem. ESA 2009: 504-515
15		Avinatan Hassidim, Jonathan A. Kelner, Huy N. Nguyen, Krzysztof Onak: Local Graph Partitions for Approximation and Testing. FOCS 2009: 22-31
14		Alexandr Andoni, Piotr Indyk, Krzysztof Onak, Ronitt Rubinfeld: External Sampling. ICALP (1) 2009: 83-94
13		Alexandr Andoni, Krzysztof Onak: Approximating edit distance in near-linear time. STOC 2009: 199-204
12		Krzysztof Onak: Testing Distribution Identity Efficiently CoRR abs/0910.3243: (2009)
	2008
11		Huy N. Nguyen, Krzysztof Onak: Constant-Time Approximation Algorithms via Local Improvements. FOCS 2008: 327-336
10		Nicholas J. A. Harvey, Jelani Nelson, Krzysztof Onak: Sketching and Streaming Entropy via Approximation Theory. FOCS 2008: 489-498
9		Krzysztof Onak: Testing Properties of Sets of Points in Metric Spaces. ICALP (1) 2008: 515-526
8		Shay Mozes, Krzysztof Onak, Oren Weimann: Finding an optimal tree searching strategy in linear time. SODA 2008: 1096-1105
7		Krzysztof Onak, Anastasios Sidiropoulos: Circular partitions with applications to visualization and embeddings. Symposium on Computational Geometry 2008: 28-37
6		Nicholas J. A. Harvey, Jelani Nelson, Krzysztof Onak: Sketching and Streaming Entropy via Approximation Theory CoRR abs/0804.4138: (2008)
5		Alexandr Andoni, Andrew McGregor, Krzysztof Onak, Rina Panigrahy: Better Bounds for Frequency Moments in Random-Order Streams CoRR abs/0808.2222: (2008)
	2007
4		Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Servedio, Andrew Wan: Testing for Concise Representations. FOCS 2007: 549-558
3		David R. Karger, Krzysztof Onak: Polynomial approximation schemes for smoothed and random instances of multidimensional packing problems. SODA 2007: 1207-1216
2		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
1		Krzysztof Onak, Pawel Parys: Generalization of Binary Search: Searching in Trees and Forest-Like Partial Orders. FOCS 2006: 379-388

Coauthor Index

1	Alexandr Andoni	[5] [13] [14] [17] [19] [22] [23] [25] [27] [30]
2	Mark de Berg	[18]
3	Artur Czumaj	[29]
4	Ilias Diakonikolas	[2] [4]
5	Alan Edelman	[28] [31]
6	Nicholas J. A. Harvey	[6] [10]
7	Avinatan Hassidim	[15] [28] [31]
8	Piotr Indyk	[14] [23]
9	David R. Karger	[3]
10	Jonathan A. Kelner	[15]
11	Robert Krauthgamer	[17] [19] [22] [25] [30]
12	Homin K. Lee	[2] [4]
13	Kevin Matulef	[2] [4]
14	Andrew McGregor	[5] [16]
15	Morteza Monemizadeh	[29]
16	Shay Mozes	[8]
17	Jelani Nelson	[6] [10]
18	Huy N. Nguyen	[11] [15] [28] [31]
19	Rina Panigrahy	[5] [16]
20	Pawel Parys	[1]
21	Dana Ron	[26] [32]
22	Michal Rosen	[26] [32]
23	Ronitt Rubinfeld	[2] [4] [14] [20] [21] [23] [26] [32]
24	Rocco A. Servedio	[2] [4]
25	Anastasios Sidiropoulos	[7] [18]
26	Christian Sohler	[29]
27	Andrew Wan	[2] [4]
28	Oren Weimann	[8]

Colors in the list of coauthors

Last update Fri May 25 01:42:58 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page