On the Streaming Complexity of Expander Decomposition
With Michael Kapralov, Mikhail Makarov and Davide Mazzali
[ICALP 2024]
Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics
With Sanjeev Khanna and Zihan Tan
[ICALP 2023] [Arxiv]
Query Complexity of the Metric Steiner Tree Problem
With Sanjeev Khanna and Zihan Tan
On Weighted Graph Sparsification by Linear Sketching
With Sanjeev Khanna and Huan Li
Sublinear Algorithm And Lower Bound For Combinatorial Problems
The Morris and Dorothy Rubinoff Award at University of Pennsylvania
A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization
With Deeparnab Chakrabarty and Sanjeev Khanna
[FOCS 2021] [Full] [Extended Version (Arxiv)] [SICOMP]
Invited to SICOMP special issue for FOCS 2021 papers
Sublinear Time Hypergraph Sparsification via Cut and Edge Sampling Queries
With Sanjeev Khanna and Ansh Nagda
[ICALP 2021] [Arxiv]
Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation
With Sampath Kannan and Sanjeev Khanna
[ICALP 2020] [Arxiv]
Space-efficient Query Evaluation over Probabilistic Event Streams
With Rajeev Alur, Kishor Jothimurugan and Sanjeev Khanna
Near-Perfect Recovery in the One-Dimensional Latent Space Model
With Sampath Kannan and Sanjeev Khanna
Network Formation under Random Attack and Probabilistic Spread
With Shahin Jabbari, Michael Kearns, Sanjeev Khanna and Jamie Morgenstern
[IJCAI 2019] [Arxiv]
Polynomial Pass Lower Bounds for Graph Streaming Algorithms
With Sepehr Assadi and Sanjeev Khanna
Sublinear Algorithms for (∆ + 1) Vertex Coloring
With Sepehr Assadi and Sanjeev Khanna
SODA Best Paper Award Invited to HALG 2020
The Beachcombers’ Problem: Walking and Searching from an Inner Point of a Line
With Xiaotie Deng, Ziwei Ji, and Chao Liao