**Round Compression for Parallel Matching Algorithms**(with Artur Czumaj, Jakub Łącki, Aleksander Mądry, Slobodan Mitrović, Piotr Sankowski)

The 50th ACM Symposium on Theory of Computing (STOC 2018).

Invited to the special issue on STOC 2018.**Fully Dynamic Maximal Independent Set with Sublinear Update Time**(with Sepehr Assadi, Baruch Schieber, Shay Solomon)

The 50th ACM Symposium on Theory of Computing (STOC 2018).**The Query Complexity of Graph Isomorphism: Bypassing Distribution Testing Lower Bounds**(with Xiaorui Sun)

The 50th ACM Symposium on Theory of Computing (STOC 2018).**Probability-Revealing Samples**(with Xiaorui Sun)

The 21st International Conference on Artificial Intelligence and Statistics (AISTATS 2018).**Communication-Efficient Distributed Learning of Discrete Distributions**(with Ilias Diakonikolas, Elena Grigorescu, Jerry Li, Abhiram Natarajan, Ludwig Schmidt)

The 31 Annual Conference on Neural Information Processing Systems (NIPS 2017).

Oral presentation.**Fast Algorithms for Parsing Sequences of Parentheses with Few Errors**(with Arturs Backurs)

The 35th ACM Symposium on Principles of Database Systems (PODS 2016).**Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond**(with Hossein Esfandiari, Mohammad T Hajiaghayi, Vahid Liaghat, Morteza Monemizadeh)

The 26rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015).**Parallel Algorithms for Geometric Graph Problems**(with Alexandr Andoni, Aleksandar Nikolov, Grigory Yaroslavtsev)

The 46th ACM Symposium on Theory of Computing (STOC 2014).**Superlinear Lower Bounds for Multipass Graph Processing**(with Venkatesan Guruswami)

The 28th IEEE Conference on Computational Complexity (CCC 2013).

Invited to a special issue of Algorithmica on Information Complexity and Applications.**On the Complexity of Learning and Testing Hyperfinite Graphs****A Near-Optimal Sublinear-Time Algorithm for Approximating the Minimum Vertex Cover Size**(with Dana Ron, Michal Rosen, Ronitt Rubinfeld)

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)

The 52nd Annual Symposium on Foundations of Computer Science (FOCS 2011).**Streaming Algorithms via Precision Sampling**(with Alexandr Andoni, Robert Krauthgamer)

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)

SIAM Journal on Computing, 41(6), 2012 (special issue on STOC 2009).

Preliminary version in 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)

Journal of Computational Geometry, 4(1), 2013.

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

**Open Problems in Data Streams, Property Testing, and Related Topics**(edited with Piotr Indyk, Andrew McGregor, Ilan Newman)

June 2011