Debmalya Panigrahi | Scholars@Duke

Debmalya Panigrahi
Associate Professor of Computer Science

Research interests: design and analysis of algorithms, theoretical computer science, combinatorial optimization

Please visit Debmalya Panigrahi's homepage for up-to-date information.

Current Appointments & Affiliations

Associate Professor of Computer Science, Computer Science, Trinity College of Arts & Sciences 2019

Contact Information

308 Research Dr, Campus Box 90129, D203 LSRC Building, Durham, NC 27708
Campus Box 90129, Durham, NC 27708
(919) 660-6545
https://www.cs.duke.edu/~debmalya

Background
Education, Training, & Certifications
- Ph.D., Massachusetts Institute of Technology 2012
Duke Appointment History
- Assistant Professor of Computer Science, Computer Science, Trinity College of Arts & Sciences 2013 - 2019
Research
Selected Grants
- Multi-objective Optimization in Internet Advertising awarded by Google Inc. 2014 - 2027
- Collaborative Research: AF: Medium: Algorithms Meets ML: Mitigating Uncertainty in Optimization awarded by National Science Foundation 2020 - 2024
- CAREER New Directions in Graph Algorithms awarded by National Science Foundation 2018 - 2023
- HDR TRIPODS: Innovations in Data Science: Integrating Stochastic Modeling, Data Representation, and Algorithms awarded by National Science Foundation 2019 - 2022
- Information Networks: RESUME: Artificial Intelligence, Algorithms, and Optimization for Responsible Reopening awarded by Army Research Office 2021 - 2022
- AitF: FULL: Collaborative Research: Optimizing Networked Systems with Limited Information awarded by National Science Foundation 2015 - 2020
- AF: Small: Allocation Algorithms in Online Systems awarded by National Science Foundation 2015 - 2019
External Relationships
- Alibaba Group Holding Limited
- Amazon.Com, Inc
- Apple Inc.
- Facebook Coporation
- Google, Inc.
- Microsoft Corporation
- Twitter INC
Publications & Artistic Works
Selected Publications
- Academic Articles
  - Li, J., D. Nanongkai, D. Panigrahi, T. Saranurak, and S. Yingchareonthawornchai. “Vertex connectivity in poly-logarithmic max-flows.” Proceedings of the Annual Acm Symposium on Theory of Computing, June 15, 2021, 317–29. https://doi.org/10.1145/3406325.3451088.
    Full Text
  - Hu, X., S. Sun, S. Patwa, D. Panigrahi, and S. Roy. “Aggregated deletion propagation for counting conjunctive query answers^∗.” Proceedings of the Vldb Endowment 14, no. 2 (January 1, 2020): 228–40. https://doi.org/10.14778/3425879.3425892.
    Full Text
  - Fung, W. S., R. Hariharan, N. J. A. Harvey, and D. Panigrahi. “A general framework for graph sparsification.” Siam Journal on Computing 48, no. 4 (January 1, 2019): 1196–1233. https://doi.org/10.1137/16M1091666.
    Full Text
  - Im, S., N. Kell, J. Kulkarni, and D. Panigrahi. “Tight bounds for online vector scheduling.” Siam Journal on Computing 48, no. 1 (January 1, 2019): 93–121. https://doi.org/10.1137/17M111835X.
    Full Text
  - Hajiaghayi, M., V. Liaghat, and D. Panigrahi. “Online node-weighted Steiner forest and extensions via disk paintings.” Siam Journal on Computing 46, no. 3 (January 1, 2017): 911–35. https://doi.org/10.1137/14098692X.
    Full Text
- Book Sections
  - Panigrahi, Debmalya. “Online Node-Weighted Problems.” In Encyclopedia of Algorithms, 1455–57. Springer New York, 2016. https://doi.org/10.1007/978-1-4939-2864-4_761.
    Full Text
  - Panigrahi, Debmalya. “Gomory-Hu Trees.” In Encyclopedia of Algorithms, 858–61. Springer New York, 2016. https://doi.org/10.1007/978-1-4939-2864-4_168.
    Full Text
  - Panigrahi, Debmalya. “Gomory–Hu Trees.” In Encyclopedia of Algorithms, 364–66. Springer US, 2008. https://doi.org/10.1007/978-0-387-30162-4_168.
    Full Text
- Other Articles
  - Azar, Y., A. Ganesh, R. Ge, and D. Panigrahi. “Online Service with Delay.” Acm Transactions on Algorithms, August 1, 2021. https://doi.org/10.1145/3459925.
    Full Text
  - Ganesh, A., B. M. Maggs, and D. Panigrahi. “Robust algorithms for TSP and steiner tree.” Leibniz International Proceedings in Informatics, Lipics, June 1, 2020. https://doi.org/10.4230/LIPIcs.ICALP.2020.54.
    Full Text
  - Cheng, Yu, Debmalya Panigrahi, and Kevin Sun. “Sparsification of Balanced Directed Graphs.” Corr, 2020.
  - Gupta, Anupam, Amit Kumar, and Debmalya Panigrahi. “Caching with Time Windows and Delays.” Corr, 2020.
  - Panigrahi, Debmalya, Shweta Patwa, and Sudeepa Roy. “Generalized Deletion Propagation on Counting Conjunctive Query Answers.” Corr, 2019.
  - Das, A., S. Gollapudi, A. Kim, D. Panigrahi, and C. Swamy. “Minimizing latency in online ride and delivery services.” The Web Conference 2018 Proceedings of the World Wide Web Conference, Www 2018, April 10, 2018. https://doi.org/10.1145/3178876.3186104.
    Full Text
  - Chawla, S., J. S. Naor, D. Panigrahi, M. Singh, and S. W. Umboh. “Timing matters: Online dynamics in broadcast games.” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), January 1, 2018. https://doi.org/10.1007/978-3-030-04612-5_6.
    Full Text
  - Freeman, Rupert, Samuel Haney, and Debmalya Panigrahi. “On the Price of Stability of Undirected Multicast Games.” Corr, 2016.
  - Azar, Yossi, Ilan Reuven Cohen, and Debmalya Panigrahi. “Online Covering with Convex Objectives and Applications.” Corr, 2014.
  - Devanur, Nikhil R., Konstantin Makarychev, Debmalya Panigrahi, and Grigory Yaroslavtsev. “Online Algorithms for Machine Minimization.” Corr, 2014.
  - Azar, Yossi, and Debmalya Panigrahi. “Online Load Balancing on Unrelated Machines with Startup Costs.” Corr, 2012.
  - Davidson, Susan B., Sanjeev Khanna, Debmalya Panigrahi, and Sudeepa Roy. “Preserving Module Privacy in Workflow Provenance.” Corr, 2010.
  - Hariharan, Ramesh, and Debmalya Panigrahi. “A Linear-time Algorithm for Sparsification of Unweighted Graphs.” Corr, 2010.
- Journal Issues
  - Andoni, A., D. Panigrahi, and M. Pilipczuk. “Editorial.” Acm Transactions on Algorithms, March 1, 2017. https://doi.org/10.1145/3038922.
    Full Text
- Reports
  - Buchbinder, Niv, Nikhil R. Devanur, and Debmalya Panigrahi. “Algorithms and Optimization under Uncertainty (NII Shonan Meeting 2017-5).,” 2017.
- Conference Papers
  - Cen, R., Y. Cheng, D. Panigrahi, and K. Sun. “Sparsification of directed graphs via cut balance.” In Leibniz International Proceedings in Informatics, Lipics, Vol. 198, 2021. https://doi.org/10.4230/LIPIcs.ICALP.2021.45.
    Full Text
  - Ganesh, A., B. M. Maggs, and D. Panigrahi. “Universal algorithms for clustering problems.” In Leibniz International Proceedings in Informatics, Lipics, Vol. 198, 2021. https://doi.org/10.4230/LIPIcs.ICALP.2021.70.
    Full Text
  - Li, J., and D. Panigrahi. “Approximate Gomory Hu Tree Is Faster Than n - 1 Max-Flows.” In Proceedings of the Annual Acm Symposium on Theory of Computing, 1738–48, 2021. https://doi.org/10.1145/3406325.3451112.
    Full Text
  - Chawla, S., J. S. Naor, D. Panigrahi, M. Singh, and S. W. Umboh. “Timing Matters: Online Dynamics in Broadcast Games.” In Acm Transactions on Economics and Computation, Vol. 9, 2021. https://doi.org/10.1145/3434425.
    Full Text
  - Deng, Y., D. Panigrahi, and H. Zhang. “Online combinatorial auctions.” In Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms, 1131–49, 2021.
  - Li, J., and D. Panigrahi. “Deterministic min-cut in poly-logarithmic max-flows.” In Proceedings Annual Ieee Symposium on Foundations of Computer Science, Focs, 2020-November:85–92, 2020. https://doi.org/10.1109/FOCS46700.2020.00017.
    Full Text
  - Gupta, A., A. Kumar, and D. Panigrahi. “Caching with time windows.” In Proceedings of the Annual Acm Symposium on Theory of Computing, 1125–38, 2020. https://doi.org/10.1145/3357713.3384277.
    Full Text
  - Jiang, Z., D. Panigrahi, and K. Sun. “Online algorithms for weighted paging with predictions.” In Leibniz International Proceedings in Informatics, Lipics, Vol. 168, 2020. https://doi.org/10.4230/LIPIcs.ICALP.2020.69.
    Full Text
  - Cohen, I., S. Im, and D. Panigrahi. “Online two-dimensional load balancing.” In Leibniz International Proceedings in Informatics, Lipics, Vol. 168, 2020. https://doi.org/10.4230/LIPIcs.ICALP.2020.34.
    Full Text
  - Anand, Keerti, Rong Ge, and Debmalya Panigrahi. “Customizing ML Predictions for Online Algorithms.” In Icml, 119:303–13. PMLR, 2020.
  - Conitzer, V., D. Panigrahi, and H. Zhang. “Learning opinions in social networks.” In 37th International Conference on Machine Learning, Icml 2020, PartF168147-3:2100–2110, 2020.
  - Conitzer, Vincent, Debmalya Panigrahi, and Hanrui Zhang. “Learning Opinions in Social Networks.” In Icml, 119:2122–32. PMLR, 2020.
  - Ganesh, Arun, Bruce M. Maggs, and Debmalya Panigrahi. “Robust Algorithms for TSP and Steiner Tree.” In Icalp, edited by Artur Czumaj, Anuj Dawar, and Emanuela Merelli, 168:54:1-54:1. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  - Jiang, Zhihao, Debmalya Panigrahi, and Kevin Sun. “Online Algorithms for Weighted Paging with Predictions.” In Icalp, edited by Artur Czumaj, Anuj Dawar, and Emanuela Merelli, 168:69:1-69:1. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  - Haney, S., M. Liaee, B. M. Maggs, D. Panigrahi, R. Rajaraman, and R. Sundaram. “Retracting graphs to cycles.” In Leibniz International Proceedings in Informatics, Lipics, Vol. 132, 2019. https://doi.org/10.4230/LIPIcs.ICALP.2019.70.
    Full Text
  - Abboud, A., R. Addanki, F. Grandoni, D. Panigrahi, and B. Saha. “Dynamic set cover: Improved algorithms and lower bounds.” In Proceedings of the Annual Acm Symposium on Theory of Computing, 114–25, 2019. https://doi.org/10.1145/3313276.3316376.
    Full Text
  - Conitzer, Vincent, Christian Kroer, Debmalya Panigrahi, Okke Schrijvers, Eric Sodomka, Nicolas E. Stier-Moses, and Chris Wilkens. “Pacing Equilibrium in First-Price Auction Markets.” In Proceedings of the 2019 Acm Conference on Economics and Computation. ACM, 2019. https://doi.org/10.1145/3328526.3329600.
    Full Text
  - Deng, Y., and D. Panigrahi. “Multi-unit supply-monotone auctions with Bayesian valuations.” In Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms, 173–92, 2019.
  - Fox, K., D. Panigrahi, and F. Zhang. “Minimum cut and minimum k-cut in hypergraphs via branching contractions.” In Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms, 881–96, 2019. https://doi.org/10.1137/1.9781611975482.54.
    Full Text
  - Gollapudi, S., K. Kollias, and D. Panigrahi. “You get what you share: Incentives for a sharing economy.” In 33rd Aaai Conference on Artificial Intelligence, Aaai 2019, 31st Innovative Applications of Artificial Intelligence Conference, Iaai 2019 and the 9th Aaai Symposium on Educational Advances in Artificial Intelligence, Eaai 2019, 2004–11, 2019.
  - Gollapudi, Sreenivas, and Debmalya Panigrahi. “Online Algorithms for Rent-Or-Buy with Expert Advice.” In Icml, edited by Kamalika Chaudhuri and Ruslan Salakhutdinov, 97:2319–27. PMLR, 2019.
  - Gupta, A., R. Krishnaswamy, A. Kumar, and D. Panigrahi. “Elastic caching.” In Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms, 143–56, 2019. https://doi.org/10.1137/1.9781611975482.10.
    Full Text
  - Im, S., D. Panigrahi, N. Kell, and M. Shadloo. “Online load balancing on related machines.” In Proceedings of the Annual Acm Symposium on Theory of Computing, 978–89, 2018. https://doi.org/10.1145/3188745.3188966.
    Full Text
  - Azar, Y., I. R. Cohen, and D. Panigrahi. “Randomized algorithms for online vector load balancing.” In Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms, 990–91, 2018. https://doi.org/10.1137/1.9781611975031.63.
    Full Text
  - Azar, Yossi, Ilan Reuven Cohen, and Debmalya Panigrahi. “Randomized Algorithms for Online Vector Load Balancing.” In Soda, edited by Artur Czumaj, 980–91. SIAM, 2018.
  - Das, Abhimanyu, Sreenivas Gollapudi, Anthony Kim, Debmalya Panigrahi, and Chaitanya Swamy. “Minimizing Latency in Online Ride and Delivery Services.” In Www, edited by Pierre-Antoine Champin, Fabien L. Gandon, Mounia Lalmas, and Panagiotis G. Ipeirotis, 379–88. ACM, 2018.
  - Im, Sungjin, Nathaniel Kell, Debmalya Panigrahi, and Maryam Shadloo. “Online load balancing on related machines.” In Stoc, edited by Ilias Diakonikolas, David Kempe, and Monika Henzinger, 30–43. ACM, 2018.
  - Gollapudi, S., R. Kumar, D. Panigrahi, and R. Panigrahy. “Partitioning orders in online shopping services.” In International Conference on Information and Knowledge Management, Proceedings, Part F131841:1319–28, 2017. https://doi.org/10.1145/10.1145/3132847.3132903.
    Full Text
  - Gollapudi, Sreenivas, Ravi Kumar, Debmalya Panigrahy, and Rina Panigrahy. “Partitioning Orders in Online Shopping Services.” In Proceedings of the 2017 Acm on Conference on Information and Knowledge Management. ACM, 2017. https://doi.org/10.1145/3132847.3132903.
    Full Text
  - Gollapudi, S., K. Kollias, D. Panigrahi, and V. Pliatsika. “Profit sharing and efficiency in utility games.” In Leibniz International Proceedings in Informatics, Lipics, Vol. 87, 2017. https://doi.org/10.4230/LIPIcs.ESA.2017.43.
    Full Text
  - Haney, S., B. Maggs, B. Maiti, D. Panigrahi, R. Rajaraman, and R. Sundaram. “Symmetric interdiction for matching problems.” In Leibniz International Proceedings in Informatics, Lipics, Vol. 81, 2017. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2017.9.
    Full Text
  - Azar, Y., A. Ganesh, R. Ge, and D. Panigrahi. “Online service with delay.” In Proceedings of the Annual Acm Symposium on Theory of Computing, Part F128415:551–63, 2017. https://doi.org/10.1145/3055399.3055475.
    Full Text
  - Gupta, A., R. Krishnaswamy, A. Kumar, and D. Panigrahi. “Online and dynamic algorithms for set cover.” In Proceedings of the Annual Acm Symposium on Theory of Computing, Part F128415:537–50, 2017. https://doi.org/10.1145/3055399.3055493.
    Full Text
  - Agarwal, P. K., K. Fox, D. Panigrahi, K. R. Varadarajan, and A. Xiao. “Faster algorithms for the geometric transportation problem.” In Leibniz International Proceedings in Informatics, Lipics, 77:71–716, 2017. https://doi.org/10.4230/LIPIcs.SoCG.2017.7.
    Full Text
  - Agarwal, Pankaj K., Kyle Fox, Debmalya Panigrahi, Kasturi R. Varadarajan, and Allen Xiao. “Faster Algorithms for the Geometric Transportation Problem.” In Socg, edited by Boris Aronov and Matthew J. Katz, 77:7:1-7:1. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
  - Ghaffari, M., D. R. Karger, and D. Panigrahi. “Random contractions and sampling for hypergraph and hedge connectivity.” In Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms, 0:1101–14, 2017. https://doi.org/10.1137/1.9781611974782.71.
    Full Text
  - Gupta, Anupam, Ravishankar Krishnaswamy, Amit Kumar, and Debmalya Panigrahi. “Online and dynamic algorithms for set cover.” In Stoc, edited by Hamed Hatami, Pierre McKenzie, and Valerie King, 537–50. ACM, 2017.
  - Azar, Y., N. Buchbinder, T. H. H. Chan, S. Chen, I. R. Cohen, A. Gupta, Z. Huang, et al. “Online Algorithms for Covering and Packing Problems with Convex Objectives.” In Proceedings Annual Ieee Symposium on Foundations of Computer Science, Focs, 2016-December:148–57, 2016. https://doi.org/10.1109/FOCS.2016.24.
    Full Text
  - Kell, N., and D. Panigrahi. “Online budgeted allocation with general budgets.” In Ec 2016 Proceedings of the 2016 Acm Conference on Economics and Computation, 419–36, 2016. https://doi.org/10.1145/2940716.2940770.
    Full Text
  - Freeman, R., S. Haney, and D. Panigrahi. “On the price of stability of undirected multicast games.” In Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 10123 LNCS:354–68, 2016. https://doi.org/10.1007/978-3-662-54110-4_25.
    Full Text
  - Kell, Nathaniel, and Debmalya Panigrahi. “Online Budgeted Allocation with General Budgets.” In Ec, edited by Vincent Conitzer, Dirk Bergemann, and Yiling Chen, 419–36. ACM, 2016.
  - Ene, A., D. Chakrabarty, R. Krishnaswamy, and D. Panigrahi. “Online Buy-at-Bulk Network Design.” In Proceedings Annual Ieee Symposium on Foundations of Computer Science, Focs, 2015-December:545–62, 2015. https://doi.org/10.1109/FOCS.2015.40.
    Full Text
  - Im, S., N. Kell, J. Kulkarni, and D. Panigrahi. “Tight Bounds for Online Vector Scheduling.” In Proceedings Annual Ieee Symposium on Foundations of Computer Science, Focs, 2015-December:525–44, 2015. https://doi.org/10.1109/FOCS.2015.39.
    Full Text
  - Azar, Y., Z. Huang, N. R. Devanur, and D. Panigrahi. “Speed scaling in the non-clairvoyant model.” In Annual Acm Symposium on Parallelism in Algorithms and Architectures, 2015-June:133–42, 2015. https://doi.org/10.1145/2755573.2755582.
    Full Text
  - Bhawalkar, K., S. Gollapudi, and D. Panigrahi. “Online set cover with set requests.” In Leibniz International Proceedings in Informatics, Lipics, 28:64–79, 2014. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.64.
    Full Text
  - Gollapudi, S., and D. Panigrahi. “Fair allocation in online markets.” In Cikm 2014 Proceedings of the 2014 Acm International Conference on Information and Knowledge Management, 1179–88, 2014. https://doi.org/10.1145/2661829.2662011.
    Full Text
  - Makarychev, Konstantin, and Debmalya Panigrahi. “Precedence-Constrained Scheduling of Malleable Jobs with Preemption.” In Icalp (1), edited by Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, 8572:823–34. Springer, 2014.
  - Fung, Wai Shing, Ramesh Hariharan, Nicholas J. A. Harvey, and Debmalya Panigrahi. “A general framework for graph sparsification.” In Stoc, edited by Lance Fortnow and Salil P. Vadhan, 71–80. ACM, 2011.
  - Dutta, Partha, Sharad Jaiswal, Debmalya Panigrahi, and Rajeev Rastogi. “A New Channel Assignment Mechanism for Rural Wireless Mesh Networks.” In Infocom, 2261–69. IEEE, 2008.
  - Naidu, K. V. M., Debmalya Panigrahi, and Rajeev Rastogi. “Detecting Anomalies Using End-to-End Path Measurements.” In Infocom, 1849–57. IEEE, 2008.
  - Panigrahi, Debmalya, Partha Dutta, Sharad Jaiswal, K. V. M. Naidu, and Rajeev Rastogi. “Minimum Cost Topology Construction for Rural Wireless Mesh Networks.” In Infocom, 771–79. IEEE, 2008.
  - Bhalgat, Anand, Ramesh Hariharan, Telikepalli Kavitha, and Debmalya Panigrahi. “An (O)over-tilde(mn) Gomory-Hu Tree Construction Algorithm for Unweighted Graphs.” In Stoc 07: Proceedings of the 39th Annual Acm Symposium on Theory of Computing, 605–14. ASSOC COMPUTING MACHINERY, 2007.
    Link to Item
  - Hariharan, R., T. Kavitha, and D. Panigrahi. “Efficient algorithms for computing all low s-t edge connectivities and related problems.” In Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms, 07-09-January-2007:127–36, 2007.
Teaching & Mentoring
Recent Courses

Some information on this profile has been compiled automatically from Duke databases and external sources. (Our About page explains how this works.) If you see a problem with the information, please write to Scholars@Duke and let us know. We will reply promptly.

Education, Training, & Certifications

Duke Appointment History

Selected Grants

External Relationships

Selected Publications

Academic Articles

Book Sections

Other Articles

Journal Issues

Reports

Conference Papers

Recent Courses