His research interests are in graph algorithms, discrete optimization, and computational geometry. He has published about 200 journal and conference papers, and several book chapters on these topics. He was an editor for the journal Algorithmica, and International Journal on Foundations of Computer Science, problems Editor for ACM Trans. on Algorithms, and currently is a columnist for SIGACT News and Associate Editor for Networks. He has served on several program committees including SODA 1997, APPROX 1999, APPROX 2000 (chair), STOC 2003, PODS 2006, SODA 2007, APPROX 2010, ESA 2010, STOC 2013, SPAA 2017. He served on the ESA Steering Committee from 2012-2016 and will chair the 2019 MAPSP Scheduling Workshop.
He received the National Science Foundation's Career Development Award, several Dept. Teaching Awards, the Dean's Teaching Excellence Award and also a CTE-Lilly Teaching Fellowship. In 2003, he and his students were awarded the "Best newcomer paper" award for the ACM PODS Conference. He received the University of Maryland's Distinguished Scholar Teacher Award in 2007, as well as a Google Research Award. In 2016, he received the European Symposium on Algorithms inaugural Test of Time Award for his work with Sudipto Guha on Connected Dominating Sets. He graduated at the top of the Computer Science Class from IIT-Kanpur.