Debmalya panigrahi

Associate Professor

Department of Computer Science

Duke University


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 Interests

My research is in Theoretical Computer Science, focusing on the Design and Analysis of Algorithms with provable properties. Specific topics of interest include:

  • Graph Algorithms, particularly the study of Cuts, Flows, and Connectivity in graphs.

  • Algorithms under Uncertainty, particularly Online Algorithms.

  • Theoretical Machine Learning, particularly its role in Beyond Worst-Case algorithm design.

  • Approximation Algorithms for Combinatorial Optimization of NP-hard problems.

  • Algorithms in the Real World, including algorithms for Online Search, Advertising, and E-commerce, in Computer, Social, and Information Networks, in Computational Economics, in Big Data environments and Database Systems, etc.

I am generally excited by any algorithms research problem, but 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.


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


I currently have openings for postdocs, graduate students, and undergraduates. 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.


My research has been funded by the National Science Foundation through various grants (including a CAREER Award), by faculty research awards from Google and Yahoo!, by the Indo-US Science and Technology Forum, and by Duke University. I gratefully acknowledge their support.

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


I have been fortunate to have received several awards and honors, some of which are listed below:

  • NSF CAREER Award.

  • Selected as a top 5% instructor based on teaching evaluations in the Trinity College of Arts and Sciences, Duke University on multiple occasions.

  • Faculty research awards from Google and Yahoo!

  • Best Paper Award at SPAA.

  • MIT Presidential Fellowship.

  • Gold medals for ranking 1st in masters at IISc and undergraduate at Jadavpur University.

  • Jagadis Bose National Science Talent Search (JBNSTS) Scholarship.

  • National Talent Search Examination (NTSE) Scholarship awarded by Govt of India.

For a more complete list of awards and honors, please see my CV.


I have taught various courses in algorithms and theoretical computer science at the graduate and undergraduate levels.

Current Course

Spring 2021. COMPSCI 330 Design and Analysis of Algorithms (undergraduate course in algorithms, will be co-taught with Prof. Rong Ge)

Spring 2021. COMPSCI 590.04 Special Topics in Computer Science: Machine Learning Algorithms (graduate course on "algorithms for ML" and "ML-augmented algorithms", will be co-taught with Prof. Rong Ge)

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


I have served on various program committees, panels, juries, etc. Some of these are listed below. For a more complete list, please see my CV.

Selected Program Committees

  • 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021.

  • 60th IEEE Symposium on Foundations of Computer Science (FOCS), 2019.

  • 47th ACM Symposium on Theory of Computing (STOC), 2016.

  • 26th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015.

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


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