# Debmalya panigrahi

### Associate Professor

### Department of Computer Science

### Duke University

## NEWS

December '21: AAAI 2022 paper

Learning Influence Adoption in Heterogeneous Networks: We give a PAC-learning framework for understanding how a label (e.g., whether a person is infected by a transmissible disease) propagates through a network where each individual node reacts differently to exposure (e.g., depending on their age, co-morbidities, etc.)

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!

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.

## about me

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.

To see the list of former students and postdocs, please click here.

### 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.

For more information about my funding, including current grants, please click here.

## 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)

For a complete list of the courses that I have taught (including links to course material), please click here.

## Contact Information

### Mailing Address

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