Lower Bounds on Flow Sparsifiers with Steiner Nodes

With Zihan Tan and Mingyang Yang

[STOC 2026] [Arxiv]

Lower Bounds on Tree Covers

With Zihan Tan and Hangyu Xu

[ITCS 2026] [Arxiv]

Cut-Preserving Vertex Sparsifiers for Planar and Quasi-bipartite Graphs

With Zihan Tan

[ICALP 2025] [Arxiv]

Paths and Intersections: Characterization of Quasi-metrics in Directed Okamura-Seymour Instances

With Zihan Tan

[SODA 2025] [Arxiv]

On the Streaming Complexity of Expander Decomposition

With Michael Kapralov, Mikhail Makarov and Davide Mazzali

[ICALP 2024] [Arxiv]

Lower Bounds on 0-Extension with Steiner Nodes

With Zihan Tan

[ICALP 2024] [Arxiv]

Towards the Characterization of Terminal Cut Functions: a Condition for Laminar Families

With Zihan Tan

[Arxiv]

An \tilde{Ω}(\sqrt{log |T|}) Lower Bound for Steiner Point Removal

With Zihan Tan

[SODA 2024] [Arxiv]

On (1+ε)-Approximate Flow Sparsifiers

With Zihan Tan

[SODA 2024] [Arxiv]

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

[SODA 2023] [Arxiv]

On Weighted Graph Sparsification by Linear Sketching

With Sanjeev Khanna and Huan Li

[FOCS 2022] [Arxiv]

Sublinear Algorithm And Lower Bound For Combinatorial Problems

[PhD Thesis]

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]

Near-linear Size Hypergraph Cut Sparsifiers

With Sanjeev Khanna and Ansh Nagda

[FOCS 2020] [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

[LICS 2020]

Near-Perfect Recovery in the One-Dimensional Latent Space Model

With Sampath Kannan and Sanjeev Khanna

[WWW 2020] [Arxiv]

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

[STOC 2019] [Arxiv]

Sublinear Algorithms for (∆ + 1) Vertex Coloring

With Sepehr Assadi and Sanjeev Khanna

[SODA 2019] [Arxiv]

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

[LATA 2016]