Assistant Professor, Theory Group

Dept. of Computer Science, Purdue University

`krq (at) purdue.edu`

Lawson 1211

My research is about the design and analysis of algorithms in theoretical computer science. I have worked on approximation algorithms, randomized algorithms, combinatorial optimization, continuous optimization, online learning, and discrete geometry. I am particularly interested in highly scalable algorithms for fundamental problems in optimization.

Graduate algorithms: **Spring 2023**, Spring 2021, and Spring 2020

Randomized algorithms: Fall 2022, Fall 2020, and Fall 2019 (with Petros Drineas)

Undergraduate algorithms: Spring 2022

Advanced topics in algorithms: Fall 2021

My research is supported in part by NSF. See DBLP for a more up-to-date list.

Quotient sparsification for submodular functions

Manuscript, Nov. 2022

(1-ε)-approximate fully dynamic densest subgraph: linear space and faster update time

Manuscript, July 2022

with Chandra Chekuri

Faster and Scalable Algorithms for Densest Subgraph and Decomposition

with Chandra Chekuri and Elfarouk Harb

Densest Subgraph: Supermodularity, Iterative Peeling, and Flow

with Chandra Chekuri and Manuel Torres

Algorithms for covering multiple submodular constraints and applications

Journal of Combinatorial Optimization, 2022

with Chandra Chekuri, Tanmay Inamdar, Kasturi Varadarajan, and Zhao Zhang

Minimum Cuts in Directed Graphs via Partial Sparsification

with Ruoxu Cen, Jason Li, Danupon Nanongkai, Debmalya Panigrahi, and Thatchaphol Saranurak

Faster Algorithms for Rooted Connectivity in Directed Graphs

with Chandra Chekuri

Isolating Cuts, (Bi-)Submodularity, and Faster Algorithms for Global Connectivity Problems

with Chandra Chekuri

Fast Approximation Algorithms for Bounded Degree and Crossing Spanning Tree Problems

with Chandra Chekuri and Manuel Torres

Online Directed Spanners and Steiner Forests

with Elena Grigorescu and Young-San Lin

Circle Packing of Planar Graphs in Nearly Linear Time

with Sally Dong and Yin Tat Lee

Fast LP-based Approximations for Geometric Packing and Covering Problems

with Chandra Chekuri and Sariel Har-Peled

ℓ_{1}‑Sparsity Approximation Bounds
for Packing Integer Programs.

with Chandra Chekuri and Manuel R. Torres

Parallelizing Greedy for Submodular Set Function Maximization in Matroids and Beyond

with Chandra Chekuri

LP Relaxation and Tree Packings for Minimum
*k*‑cut

with Chandra Chekuri and Chao Xu

On Approximating (Sparse) Covering Integer Programs

with Chandra Chekuri

Submodular Function Maximization in Parallel via the Multilinear Relaxation

with Chandra Chekuri

Fast Approximations for Metric‑TSP via Linear Programming

arXiv 2018

with Chandra Chekuri

Randomized MWU for Positive LPs

with Chandra Chekuri

Approximation Algorithms for Polynomial Expansion and Low‑Density Graphs

SIAM J. Comput. (SICOMP)
2017

ESA
2015

with Sariel Har-Peled

Approximating the Held‑Karp Bound for Metric TSP in Nearly Linear Time

with Chandra Chekuri

Near‑Linear‑Time Approximation Schemes for some Implicit Fractional Packing Problems

with Chandra Chekuri

A Fast Approximation for Maximum Weight Matroid Intersection

with Chandra Chekuri

Streaming Algorithms for Submodular Function Maximization

with Chandra Chekuri and Shalmoli Gupta

Online Learning with Adversarial Delays

with Daniel Khashabi