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 extremely scalable algorithms for fundamental problems in optimization.

**Purdue is hiring in Theory! (Again!)** Click here for the posting.

**Joint Theory Seminar. **This semester we are running a joint Theory Seminar with Michigan, on Friday's at 10:00AM EST over Zoom. See
here for the schedule and more information. Please send me an email if you would like to give a talk!

**Reading group. **There is a student-led reading
group that meets Thursday nights at 5:15 PM EST over Zoom. See here for more information including a form to
sign up for emails. It's a great place to start if you are interested in theory at Purdue.

**Fall 2020: Randomized Algorithms**

Spring 2020: Graduate Algorithms

Fall 2019: Randomized Algorithms (with Petros Drineas)

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

Parallelizing Greedy for Submodular Set Function Maximization in Matroids and Beyond

with Chandra Chekuri

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

with Chandra Chekuri and Manuel R. Torres

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 Kashabi