Scholars@Duke

• Background
• 

  Education, Training, & Certifications

  • Ph.D., Massachusetts Institute of Technology 2012
• 

  Previous Appointments & Affiliations

  • 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
  • Information Networks: RESUME: Artificial Intelligence, Algorithms, and Optimization for Responsible Reopening awarded by Army Research Office 2021 - 2022
  • HDR TRIPODS: Innovations in Data Science: Integrating Stochastic Modeling, Data Representation, and Algorithms awarded by  National Science Foundation 2019 - 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
• Publications & Artistic Works
• 

  Selected Publications

  • Academic Articles

    • Li, J., D. Panigrahi, and T. Saranurak. “A Nearly Optimal All-Pairs Min-Cuts Algorithm in Simple Graphs.” Proceedings  Annual Ieee Symposium on Foundations of Computer Science, Focs 2022-February (January 1, 2022): 1124–34. https://doi.org/10.1109/FOCS52979.2021.00111.
       Full Text
    • 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
    • Chakrabarty, D., A. Ene, R. Krishnaswamy, and D. Panigrahi. “Online buy-at-bulk network design.” Siam Journal on Computing 47, no. 4 (January 1, 2018): 1505–28. https://doi.org/10.1137/16M1117317.
       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,” December 10, 2014.
       Link to Item
    • Devanur, Nikhil, Konstantin Makarychev, Debmalya Panigrahi, and Grigory Yaroslavtsev. “Online Algorithms for Machine Minimization,” March 3, 2014.
       Link to Item
    • Azar, Yossi, and Debmalya Panigrahi. “Online Load Balancing on Unrelated Machines with Startup Costs,” March 20, 2012.
       Link to Item
    • Hariharan, Ramesh, and Debmalya Panigrahi. “A Linear-time Algorithm for Sparsification of Unweighted Graphs,” May 5, 2010.
       Link to Item
    • Davidson, Susan B., Sanjeev Khanna, Debmalya Panigrahi, and Sudeepa Roy. “Preserving Module Privacy in Workflow Provenance.” 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., J. Li, D. Nanongkai, D. Panigrahi, T. Saranurak, and K. Quanrud. “Minimum Cuts in Directed Graphs via Partial Sparsification.” In Proceedings  Annual Ieee Symposium on Foundations of Computer Science, Focs, 2022-February:1147–58, 2022. https://doi.org/10.1109/FOCS52979.2021.00113.
       Full Text
    • Cen, R., J. Li, and D. Panigrahi. “Augmenting Edge Connectivity via Isolating Cuts.” In Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms, 2022-January:3237–52, 2022.
    • Gupta, A., A. Kumar, and D. Panigrahi. “A Hitting Set Relaxation for k-Server and an Extension to Time-Windows.” In Proceedings  Annual Ieee Symposium on Foundations of Computer Science, Focs, 2022-February:504–15, 2022. https://doi.org/10.1109/FOCS52979.2021.00057.
       Full Text
    • 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.
    • Anand, K., R. Ge, A. Kumar, and D. Panigrahi. “A Regression Approach to Learning-Augmented Online Algorithms.” In Advances in Neural Information Processing Systems, 36:30504–17, 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
    • 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.
    • 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.
    • Anand, Keerti, Rong Ge, and Debmalya Panigrahi. “Customizing ML Predictions For Online Algorithms.” In International Conference on Machine Learning, Vol 119, Vol. 119, 2020.
       Link to Item
    • Conitzer, Vincent, Debmalya Panigrahi, and Hanrui Zhang. “Learning Opinions in Social Networks.” In International Conference on Machine Learning, Vol 119, Vol. 119, 2020.
       Link to Item
    • 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.
    • 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
    • Gollapudi, Sreenivas, and Debmalya Panigrahi. “Online Algorithms for Rent-or-Buy with Expert Advice.” In International Conference on Machine Learning, Vol 97, Vol. 97, 2019.
       Link to Item
    • 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
    • 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.
    • Azar, Yossi, Ilan Reuven Cohen, and Debmalya Panigrahi. “Randomized Algorithms for Online Vector Load Balancing.” In Soda’18: Proceedings of the Twenty Ninth Annual Acm Siam Symposium on Discrete Algorithms, 980–91. ASSOC COMPUTING MACHINERY, 2018.
       Link to Item
    • 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.
    • Deng, Y., D. Panigrahi, and B. Waggoner. “The complexity of stable matchings under substitutable preferences.” In 31st Aaai Conference on Artificial Intelligence, Aaai 2017, 480–86, 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
    • 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
    • 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
    • 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

  • COMPSCI 330: Introduction to the Design and Analysis of Algorithms 2022
  • COMPSCI 290: Topics in Computer Science 2021
  • COMPSCI 330: Introduction to the Design and Analysis of Algorithms 2021
  • COMPSCI 590: Advanced Topics in Computer Science 2021
  • COMPSCI 230: Discrete Math for Computer Science 2020
  • COMPSCI 330: Introduction to the Design and Analysis of Algorithms 2020

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.