Debmalya panigrahi
Professor and Associate Chair
Department of Computer Science
Duke University
NEWS
February '25: A couple of our papers were accepted to STOC 2025. One paper, titled "Network Unreliability in Almost-Linear Time", gives a faster algorithm for the problem of determining the probability that a network gets disconnected when edges fail probabilistically in an independent manner. The running time of our algorithm is optimal up to sub-polynomial (lower order) terms. The other paper, titled "Tight Results for Online Convex Paging", gives online algorithms with tight bounds in the context of the classical paging problem but for a large class of objectives spanning fairness considerations beyond just minimizing the number of page misses. Congratulations to all co-authors, especially to my student Ruoxu Cen for being the lead researcher for the first paper!
January '25: I started in a new role as Associate Chair of the CS department. Go Duke CS!
November '24: I am finally (almost) done with the SODA 25 PC, which I was co-chairing with Yossi Azar this year. See the list of accepted papers!
October '24: Our paper "Learning-Augmented Approximation Algorithms for Maximum Cut and Related Problems" was accepted to Neurips 2024. In this paper, we show how a weak signal about an optimal solution can lead to approximation results for a broad range of maximization problems that go beyond existing worst-case bound. Congratulations to all co-authors!
August '24: I was at this great workshop at TTI Chicago on learning-augmented algorithms.
July - August '24: I was at this wonderful workshop at the National University of Singapore in July. Later, we went on a trip to Cambodia and Thailand, which was also wonderful!
July '24: I am back at Duke after spending a wonderful year on sabbatical at Berkeley (fall 2023 at the Simons Institute and spring 24 at Google Research and UC Berkeley). Many thanks to the severa people who hosted me during the sabbatical and made it a very enjoyable year!
June '24: Our paper "Vertex Connectivity in Poly-logarithmic Max-flows" was accepted to the Journal of the ACM. This is the full version of our STOC 2021 paper where we gave a faster algorithm for the problem of determining the minimum number of vertices whose removal disconnects a graph. Congratulations to
June '24: We went on a trip to Chile, where I also gave a talk at the University of Chile. Many thanks to Jose Correa for his warm hospitality!
February '24: Our paper "Hypergraph Unreliability in Quasi-Polynomial Time" was accepted to STOC 2024. This paper gives the first approximation algorithm for the problem of estimating the probability that a hypergraph stays connected when every hyperedge fails independently with a given probability. Congratulations to all co-authors, especially to Ruoxu who led this research!
about me
I am a Professor of Computer Science at Duke University, where I currently also serve as Associate Chair. Previously, I have (briefly) been at Microsoft Research and Bell Labs, and have been a visitor at Google Research and the Simons Institute for Theory of Computing. I obtained my PhD in theoretical computer science at the Massachusetts Institute of Technology under the supervision of Prof. David Karger by defending this. Prior to that, I studied at the Indian Institute of Science (advised by Prof. Ramesh Hariharan) and at Jadavpur University. A long time ago, I grew up in the industrial town of Durgapur where I went to St. Xavier's School.
For those interested, here is a copy of my CV.
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 from a few years ago, 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
Ruoxu Cen (4th year PhD student)
Anish Hebbar (2nd year PhD student)
To see the list of former students and postdocs, please click here.
Funding
My research has been funded mostly by the National Science Foundation through its various programs (including a CAREER award). I have also been supported by 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 2024. COMPSCI 632 Approximation Algorithms
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