Debmalya panigrahi

Professor 

Department of Computer Science

Duke University

NEWS

about me

I am a Professor of Computer Science at Duke University. 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, 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

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