Constant-time approximation algorithms via local improvements HN Nguyen, K Onak 2008 49th Annual IEEE Symposium on Foundations of Computer Science, 327-336, 2008 | 170 | 2008 |

Parallel algorithms for geometric graph problems A Andoni, A Nikolov, K Onak, G Yaroslavtsev Proceedings of the forty-sixth annual ACM symposium on Theory of computing …, 2014 | 144 | 2014 |

Local graph partitions for approximation and testing A Hassidim, JA Kelner, HN Nguyen, K Onak 2009 50th Annual IEEE Symposium on Foundations of Computer Science, 22-31, 2009 | 131 | 2009 |

Sketching and streaming entropy via approximation theory NJA Harvey, J Nelson, K Onak 2008 49th Annual IEEE Symposium on Foundations of Computer Science, 489-498, 2008 | 114 | 2008 |

Approximating edit distance in near-linear time A Andoni, K Onak SIAM Journal on Computing 41 (6), 1635-1648, 2012 | 111 | 2012 |

Polylogarithmic approximation for edit distance and the asymmetric query complexity A Andoni, R Krauthgamer, K Onak 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 377-386, 2010 | 109 | 2010 |

Testing for concise representations I Diakonikolas, HK Lee, K Matulef, K Onak, R Rubinfeld, RA Servedio, ... 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), 549-558, 2007 | 109 | 2007 |

Streaming algorithms via precision sampling A Andoni, R Krauthgamer, K Onak 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, 363-372, 2011 | 106 | 2011 |

Maintaining a large matching and a small vertex cover K Onak, R Rubinfeld Proceedings of the forty-second ACM symposium on Theory of computing, 457-464, 2010 | 105 | 2010 |

Scalable fair clustering A Backurs, P Indyk, K Onak, B Schieber, A Vakilian, T Wagner International Conference on Machine Learning, 405-413, 2019 | 90 | 2019 |

Streaming algorithms for estimating the matching size in planar graphs and beyond H Esfandiari, M Hajiaghayi, V Liaghat, M Monemizadeh, K Onak ACM Transactions on Algorithms (TALG) 14 (4), 1-23, 2018 | 90 | 2018 |

A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size K Onak, D Ron, M Rosen, R Rubinfeld Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete …, 2012 | 75 | 2012 |

Round compression for parallel matching algorithms A Czumaj, J Łacki, A Madry, S Mitrovic, K Onak, P Sankowski SIAM Journal on Computing 49 (5), STOC18-1-STOC18-44, 2019 | 73 | 2019 |

Superlinear lower bounds for multipass graph processing V Guruswami, K Onak Algorithmica 76 (3), 654-683, 2016 | 70 | 2016 |

Fully Dynamic Maximal Independent Set with Sublinear in *n* Update TimeS Assadi, K Onak, B Schieber, S Solomon Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete …, 2019 | 56 | 2019 |

Fat polygonal partitions with applications to visualization and embeddings M de Berg, K Onak, A Sidiropoulos arXiv preprint arXiv:1009.1866, 2010 | 52* | 2010 |

Generalization of binary search: Searching in trees and forest-like partial orders K Onak, P Parys 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06 …, 2006 | 48 | 2006 |

Finding an optimal tree searching strategy in linear time S Mozes, K Onak, O Weimann Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete …, 2008 | 41 | 2008 |

Communication-efficient distributed learning of discrete distributions I Diakonikolas, E Grigorescu, J Li, A Natarajan, K Onak, L Schmidt Advances in Neural Information Processing Systems, 6391-6401, 2017 | 36 | 2017 |

Planar graphs: Random walks and bipartiteness testing A Czumaj, M Monemizadeh, K Onak, C Sohler Random Structures & Algorithms 55 (1), 104-124, 2019 | 28* | 2019 |