Department of Computer Science
April '21: ICALP 2021 papers
Sparsification of directed graphs: Graph sparsification is a standard tool for reducing the size of an input graph by making it sparse while preserving cut properties. This enables various cut algorithms to run (faster) on the sparsifier instead of the original input graph. But, one drawback of this technique is that it applies only to undirected graphs. Indeed, for directed graphs, there are well-known examples that cannot be sparsified. In this paper, we parameterize directed graphs via a property called cut balance and show that the extent of sparsification gracefully degrades with the cut balance of the input directed graph. In particular, undirected graph has perfect cut balance and can be sparsified to the optimal extent, and there is an entire continuum of directed graphs stretching all the way to the bottleneck examples that have the worst cut balance.
Universal algorithms for clustering: In clustering problems, we are given a set of points that have to be grouped (and often a group leader or center chosen) so as to minimize some natural objective that reflects the cohesion of the groups. In this paper, we give universal algorithms for the classic clustering objectives of k-median, k-means, and k-center. In the universal setting, a set of potential points are given upfront and their grouping has to be decided in a manner that (approximately) optimizes the given objective for any set of points that actually realize from the potential set.
February '21: STOC 2021 papers
Gomory-Hu trees: How do we find the connectivity between all pairs of vertices in a graph? One natural answer is to run a maxflow algorithm for every vertex pair to find their connectivity. In 1961, Gomory and Hu gave a more elegant answer to this question by showing that this can be done in just n-1 maxflow calls. Even after almost 60 years of their work, improving Gomory and Hu's algorithm for this problem remains a major open question in graph algorithms. In this paper, we make progress toward this goal by showing the following: we give an algorithm that uses only polylog(n) maxflow calls instead of n-1 and finds the connectivity between all pairs of vertices up to an arbitrarily small constant approximation.
Vertex connectivity: The vertex conectivity of a graph is the smallest number of vertices whose removal disconnects the graph. In this paper, we give an algorithm for computing the vertex connectivity of a graph by running polylog(n) maxflow algorithms. This is the first improvement in the running time of the vertex connectivity problem since the work of Henzinger, Rao, and Gabow in 1996.
September '20: SODA 2021 paper
Combinatorial auctions in online settings: Combinatorial auctions are a method for selling heterogeneous items to buyers so as to maximize their cumulative (social) welfare. In this paper, we consider the scenario where these items arrive online over time, and have expiry dates by which they need to be sold. We obtain a sharp characterization of when we can design nearly optimal combinatorial auctions online. If the valuations of items by buyers are given a submodular function (a widely studied class), we design an (approximately) welfare-maximizing auction. In contrast, if the valuations are from the slightly more general XOS class, we show that there does not exist any approximately optimal auction in a rather strong sense.
September '20: VLDB 2021 paper on deletion propagation in databases.
July '20: FOCS 2020 paper
Deterministic algorithm for minimum cut: The minimum cut problem asks for the smallest cardinality/weight of edges whose removal disconnects a graph. We give a deterministic algorithm for finding the minimum cut of an undirected graph using polylog(n) maxflow calls. This is the first improvement in the running time of deterministic algorithms for this problem since the early 1990s.
May '20: ICML 2020 papers
April '20: ICALP 2020 papers
February '20: STOC 2020 paper
I am an Associate Professor of Computer Science at Duke University. Before coming to Duke in 2013, I spent one year as a postdoctoral research in the theory group at Microsoft Research Redmond, where I did research in algorithms. In 2012, I obtained my PhD in theoretical computer science at MIT under the supervision of Prof. David Karger by defending this. Before coming to MIT, I worked at Bell Labs in Bangalore for a year, where I did research on algorithms and networks. I obtained my bachelors' and masters' degrees in Computer Science and Engineering at Jadavpur University, Kolkata in 2004 and IISc, Bangalore in 2006 respectively. At IISc, I did research in algorithms under the supervision of Prof. Ramesh Hariharan. A long time ago, I grew up in the industrial town of Durgapur where I went to St. Xavier's School.
My CV is available here.
I am broadly interested in theoretical computer science, particularly in the design and analysis of algorithms. My two main research thrusts are graph algorithms and algorithms under uncertainty. In graph algorithms, I am interested in the study of network flows, graph cuts, and connectivity. Some recent highlights include the fastest deterministic algorithm to find a minimum cut of an undirected graph, the fastest (randomized) algorithms for finding a minimum vertex cut and a minimum cut of a directed graph, and the fastest algorithm for finding the connectivity of all pairs of vertices in an undirected graph. In algorithms under uncertainty, I am interested in both classical online algorithms, and also the design of algorithms that leverage machine learning to overcome worst-case performance barriers. Some recent highlights include new LP relaxations and algorithms for $k$-server and caching problems, and learning-augmented algorithms for fundamental online problems such as weighted caching and ski rental. I also work in approximation algorithms, combinatorial optimization, and algorithmic game theory.
In addition to theoretical research, I am also interested in the design of algorithms for practical problems. This includes algorithms for online search, advertising, social networks, and e-commerce, the design and management of computer networks, database management and query processing algorithms, and algorithms with applications in artificial intelligence. I have collaborated with researchers in these areas to design algorithms that are practical, implementable, and scalable. Most of this work has been published in peer-reviewed venues in the application areas, and some of it has led to patents and deployment in prototypes or products.
For a sample of my current research directions, see here.
I am part of the theory group and am also affiliated/collaborate with the CS-econ, AI/ML, and database groups at Duke.
I currently have openings for graduate students and undergraduates. I also occasionally have opening for postdocs. Please see here for details.
Ruoxu Cen (1st year PhD student)
Kevin Sun (3rd year PhD student)
To see the list of former students and postdocs, please click here.
My research has been funded by the National Science Foundation, the Army Research Office, Google, Yahoo!, the Indo-US Science and Technology Forum, and Duke University. I gratefully acknowledge their support.
For more information about my funding, including current grants, please click here.
Fall 2021. COMPSCI 290 Special Topics: Great Ideas in Computer Science (an introduction to computer science from the perspective of the big ideas, conflicts, and questions that computer science has brought to the fore: the course will include discussions on the historical perspective of the emergence of computer science and its meteoric rise in less than a century, how computer science relates to mathematics, engineering, and other branches of science, the role of computer science in shaping human thought and knowledge in a modern world, and some of the big futuristic questions that computer science faces today in theory and practice)
For a complete list of the courses that I have taught (including links to course material), please click here.
Duke University, Campus Box 90129
308 Research Drive (LSRC Building), Room D203
Durham, NC 27708 USA
Tel: +1 (919) 660-6545
Fax: +1 (919) 660-6519
The fastest and preferred way to reach me is by email. My username is my first name and the domain is cs.duke.edu