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
Faster exact and approximation algorithms for packing and covering matroids via push-relabel
Manuscript, July. 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