I am a final year PhD student in the CS Theory group at UIUC, working with Chandra Chekuri and Sariel Har-Peled.

Research

1-Sparsity Approximation Bounds for Packing Integer Programs. With Chandra Chekuri and Manuel R. Torres. 2018.

Parallelizing Greedy for Submodular Set Function Maximization in Matroids and Beyond. With Chandra Chekuri. 2018. [slides (purdue)] [slides (northwestern)]

Approximating Optimal Transport with Linear Programs. To appear in SOSA 2019.

LP Relaxation and Tree Packings for Minimum k-cut. With Chandra Chekuri and Chao Xu. To appear in SOSA 2019.

On Approximating (Sparse) Covering Integer Programs. With Chandra Chekuri. To appear in SODA 2019.

Submodular Function Maximization in Parallel via the Multilinear Relaxation. With Chandra Chekuri. To appear in SODA 2019. [slides (purdue)] [slides (northwestern)] [slides (allerton)]

Fast and Deterministic Approximations for k-cut. 2018.

Fast Approximations for Metric-TSP via Linear Programming. With Chandra Chekuri. 2018. [slides (uiuc)] [slides (ismp)] [slides (birs)] [video (birs)]

Randomized MWU for Positive LPs. With Chandra Chekuri. SODA 2018. [slides (soda)]

Approximation Algorithms for Polynomial Expansion and Low-Density Graphs. With Sariel Har-Peled. SIAM J. Comput. (SICOMP), 46(6) 1712-1744, 2017. Preliminary version in ESA 2015. [slides (uiuc)] [notes]

Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Time. With Chandra Chekuri. FOCS 2017. [slides (focs)] [slides (ismp '18)] [slides (birs)] [video (focs)] [video (birs)]

Near-Linear-Time Approximation Schemes for some Implicit Fractional Packing Problems. With Chandra Chekuri. SODA 2017. [slides (soda)] [slides (barbados)]

A Fast Approximation for Maximum Weight Matroid Intersection. With Chandra Chekuri. SODA 2016. [slides (soda)] [slides (uiuc)]

Online Learning with Adversarial Delays. With Daniel Khashabi. NIPS 2015. [poster]

Streaming Algorithms for Submodular Function Maximization. With Chandra Chekuri and Shalmoli Gupta. ICALP 2015. [slides (bonn)] [video (bonn)]