# Debmalya panigrahi

## NEWS

• November '21: See our new paper (on arxiv) for min-cut for all vertex pairs that breaks Gomory and Hu's 60-year old bound for this problem!

• October '21: SODA 2022 papers

• Connectivity Augmentation and Splitting-Off: We give new algorithms for the edge connectivity augmentation and edge splitting-off problems using the isolating cuts framework that we introduced in a FOCS 2020 paper. This is the first improvement for these problems since the work of Benczur and Karger in 2000.

• Online Graph Algorithms with ML Predictions: We give an algorithmic framework for network design problems like Steiner tree, Steiner forest, and facility location in the online algorithms with predictions model. One of the main contributions is a new model for measuring the error of a prediction for metric/graph problems that takes into account both the possibility of inaccurate predictions and complete mispredictions.

• September '21: NeurIPS 2021 paper

• Regression for Learning-Augmented Online Algorithms: We bring a regression approach to the area of learning-augmented online algorithms. Our mian contribution is a regression framework and the design of a new loss function that helps make predictions using a PAC learning model for a broad class of online algorithms.

• August '21: FOCS 2021 papers

• Minimum Cut in Directed Graphs: We give an algorithm to find a minimum cut in a directed graph using (roughly) \tilde{O}(\sqrt{m}) max-flow calls. This is the first improvement for the problem since the work of Hao and Orlin in 1992.

• All-Pairs Minimum Cuts: We give an algorithm that finds the edge connectivity between all pairs of vertices in \tilde{O}(n^2) time for simple graphs. This is optimal if the edge connectivity of every pair is represented explicitly.

• Online Algorithm for k-Server and Extensions: We give an algorithm for the k-server problem and its extension to time windows that has a poly-logarithmic competitive ratio. Our main technical contribution is a new "hitting set" LP formulation of the k-server problem that could be useful in resolving the randomized k-server conjecture. (Our competitive ratio currently depends on the size and aspect ratio of the metric space in addition to the number of servers k.)

• April '21: ICALP 2021 papers

• Sparsification of directed graphs: It is well-known that undirected graphs admit cut sparsifiers, and directed graphs do not. We give a more refined view by parametrizing directed graphs using a notion called cut balance and give tight results for sparsification as a function of this parameter. This is one of the first attempts at trying to understand cut sparsification for directed graphs.

• Universal algorithms for clustering: We give robust clustering algorithms for standard objectives like k-median, k-means, and k-center, where a set of possible inputs is available offline, but the actual input realizes online.

• February '21: STOC 2021 papers

• Approximate Gomory-Hu trees: We give an algorithm that uses only polylog(n) maxflow calls instead of n-1 and finds the edge connectivity between all pairs of vertices up to an arbitrarily small constant approximation. Previously, the best known was n-1 max-flows to find exact all-pairs connectivities from the work of Gomory and Hu in 1961.

• Vertex connectivity: 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.

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.

## Research

### Research Interests

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.

### Publications

A complete list of my publications (along with download links to papers) is available here (arranged chronologically) and here (arranged by topic). You can also download my PhD thesis here.

## Research group

### Openings

I currently have openings for graduate students and undergraduates. I also occasionally have opening for postdocs. Please see here for details.

### Current Students

Keerti Anand (3rd year PhD student, jointly advised with Prof. Rong Ge)

Ruoxu Cen (1st year PhD student)

Kevin Sun (3rd year PhD student)

I also often work with Xiao Hu and Hanrui Zhang.

### Funding

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.

## teaching

### Current Course

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)

## Contact Information

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

### E-Mail

The fastest and preferred way to reach me is by email. My username is my first name and the domain is cs.duke.edu