Publications

This page lists my publications in reverse chronological order. If you want to see my publications organized by topic, please click here.

2023

  • Ruoxu Cen, William He, Jason Li, Debmalya Panigrahi.
    Steiner Connectivity Augmentation and Splitting-off in Poly-logarithmic Maximum Flows.
    SODA 2023.

  • Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak.
    Near-Linear Time Approximations for Cut Problems via Fair Cuts.
    SODA 2023.

2022

  • Anupam Gupta, Debmalya Panigrahi, Bernardo Subercaseaux, Kevin Sun.
    Augmenting Online Algorithms with ε-Accurate Predictions. [pdf]
    NeurIPS 2022.

  • MohammadTaghi Hajiaghayi, MohammadReza Khani, Debmalya Panigrahi, Max Springer.
    Online Algorithms for the Santa Claus Problem. [pdf]
    NeurIPS 2022.

  • Sreenivas Gollapudi, Kostas Kollias, Debmalya Panigrahi.
    The Pit-Stop Problem: How to Plan Your Next Road Trip. [pdf]
    SIGSPATIAL 2022.

  • Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak, Ohad Trabelsi.
    Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time. [pdf]
    FOCS 2022.

  • Keerti Anand, Rong Ge, Amit Kumar, Debmalya Panigrahi.
    Online Algorithms with Multiple Predictions. [pdf]
    ICML 2022.

  • Ruoxu Cen, Jason Li, Debmalya Panigrahi.
    Edge-Connectivity Augmentation in Near-Linear Time. [pdf]
    STOC 2022.

  • Xiao Hu, Yuxi Liu, Haibo Xiu, Pankaj K. Agarwal, Debmalya Panigrahi, Sudeepa Roy, Jun Yang.
    Selectivity Functions of Range Queries are Learnable. [pdf]
    SIGMOD 2022.

  • Vincent Conitzer, Debmalya Panigrahi, Hanrui Zhang.
    Learning     Influence Adoption in Heterogeneous Networks.
    AAAI 2022.

  • Ruoxu Cen, Jason Li, Debmalya Panigrahi.
    Augmenting Edge Connectivity via Isolating Cuts. [pdf]
    SODA 2022.

  • Yossi Azar, Debmalya Panigrahi, Noam Touitou.
    Online Graph Algorithms with Predictions. [pdf]
    SODA 2022.

2021

  • Keerti Anand, Rong Ge, Amit Kumar, Debmalya Panigrahi.
    A Regression Approach to Learning-Augmented Online Algorithms. [pdf]
    NeurIPS 2021.

  • Jason Li, Debmalya Panigrahi, and Thatchaphol Saranurak.
    A Nearly Optimal All-Pairs Minimum Cuts Algorithm in Simple Graphs. [pdf]
    FOCS 2021.

  • Ruoxu Cen, Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Kent Quanrud, and Thatchaphol Saranurak.
    Minimum Cuts in Directed G    raphs via Partial Sparsification. [pdf]
    FOCS 2021.

  • Anupam Gupta, Amit Kumar, Debmalya Panigrahi.
    A Hitting Set Relaxation for k-Server and an Extension to Time Windows. [pdf]
    FOCS 2021.

  • Ruoxu Cen, Yu Cheng, Debmalya Panigrahi, and Kevin Sun.
    Sparsification of Directed Graphs via Cut Balance. [pdf]
    ICALP 2021.

  • Arun Ganesh, Bruce Maggs, and Debmalya Panigrahi.
    Universal Algorithms for Clustering Problems. [pdf]
    ICALP 2021.

  • Jason Li and Debmalya Panigrahi.
    Approximate Gomory-Hu tree is Faster than n-1 Max-flows. [pdf]
    STOC 2021.

  • Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, and Sorrachai Yingchareonthawirnchai.
    Vertex Connectivity in Poly-logarithmic Max-flows. [pdf]
    STOC 2021.

  • Yuan Deng, Debmalya Panigrahi, and Hanrui Zhang.
    Online Combinatorial Auctions. [pdf]
    SODA 2021.

  • Xiao Hu, Shouzhuo Sun, Shweta Patwa, Debmalya Panigrahi, and Sudeepa Roy.
    Aggregated Deletion Propagation for Counting Conjunctive Query Answers    . [pdf]
    VLDB 2021.

2020

  • Jason Li, Debmalya Panigrahi.
    Deterministic Min-cut in Poly-logarithmic Max-flows. [pdf]
    FOCS 2020.

  • Keerti Anand, Rong Ge, Debmalya Panigrahi.
    Customizing ML Predictions for Online Algorithms.     [pdf]
    ICML 2020.

  • Vincent Conitzer, Debmalya Panigrahi, Hanrui Zhang. [pdf]
    Learning Opinions in Social Networks.
    ICML 2020.

  • Arun Ganesh, Bruce Maggs, Debmalya Panigrahi.
    Robust Algorithms for TSP and Steiner Tree. [    pdf]
    ICALP 2020.

  • Zhihao Jiang, Debmalya Panigrahi, Kevin Sun.
    Online Algorithms for Weighted Paging with Predictions. [    pdf]
    ICALP 2020.

  • Ilan Cohen, Sungjin Im, Debmalya Panigrahi.
    Online Algorithms for Two-dimensional Load Balancing. [    pdf]
    ICALP 2020.

  • Anupam Gupta, Amit Kumar, Debmalya Panigrahi.
    Caching with Time Windows. [    pdf]
    STOC 2020.

2019

  • Samuel Haney, Mehraneh Liaee, Bruce M. Maggs, Debmalya Panigrahi, Rajmohan Rajaraman, Ravi Sundaram.
    Retracting Graphs to Cycles. [    pdf]
    ICALP 2019.

  • Sreenivas Gollapudi, Debmalya Panigrahi.
    Online Algorithms for Rent-Or-Buy with Expert Advice. [    pdf]
    ICML 2019.

  • Amir Abboud, Raghavendra Addanki, Fabrizio Grandoni, Debmalya Panigrahi, Barna Saha.
    Dynamic Set Cover: Improved Algorithms and Lower Bounds. [    pdf]
    STOC 2019.

  • Vincent Conitzer, Christian Kroer, Debmalya Panigrahi, Okke Schrijvers, Eric Sodomka, Nicolas Stier-Moses, Chris Wilkens.
    Pacing Equilibrium in First-Price Auction Markets.
    EC 2019.

  • Sreenivas Gollapudi, Kostas Kollias, Debmalya Panigrahi.
    You Get What You Share: Incentives for a Sharing Economy. [    pdf]
    AAAI 2019.

  • Yuan Deng, Debmalya Panigrahi.
    Multi-unit Supply-monotone Auctions with Bayesian valuations. [    pdf]
    SODA 2019.

  • Kyle Fox, Debmalya Panigrahi, Fred Zhang.
    Minimum Cut and Minimum k-Cut in Hypergraphs via Branching Contractions. [    pdf]
    SODA 2019.

  • Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, Debmalya Panigrahi.
    Elastic Caching. [    pdf]
    SODA 2019.

2018

  • Shuchi Chawla, Joseph (Seffi) Naor, Debmalya Panigrahi, Mohit Singh, Seeun Umboh.
    Timing Matters: Online Dynamics in Broadcast Games. [    pdf]
    WINE 2018.

  • Sungjin Im, Nathaniel Kell, Debmalya Panigrahi, Maryam Shadloo.
    Online Load Balancing on Related Machines. [    pdf]
    STOC 2018.

  • Abhimanyu Das, Anthony Kim, Sreenivas Gollapudi, Debmalya Panigrahi, Chaitanya Swamy.
    Minimizing Latency in Online Ride and Delivery Services. [    pdf]
    WWW 2018.
    Honorable Mention for Best Paper Award

  • Yossi Azar, Ilan Cohen, Debmalya Panigrahi.
    Randomized Algorithms for Online Vector Load Balancing. [    pdf]
    SODA 2018.

2017

  • Sreenivas Gollapudi, Ravi Kumar, Debmalya Panigrahi, Rina Panigrahy.
    Partitioning Orders in Online Shopping Services. [    pdf]
    CIKM 2017.

  • Sreenivas Gollapudi, Kostas Kollias, Debmalya Panigrahi, Venetia Pliatsika.
    Profit Sharing and Efficiency in Utility Games. [    pdf]
    ESA 2017.

  • Samuel Haney, Bruce Maggs, Biswaroop Maiti, Debmalya Panigrahi, Rajmohan Rajaraman, Ravi Sundaram.
    Symmetric Interdiction for Matching Problems. [    pdf]
    APPROX 2017.

  • Pankaj K. Agarwal, Kyle Fox, Debmalya Panigrahi, Kasturi Varadarajan, Allen Xiao.
    Faster Algorithms for the Geometric Transportation Problem. [    pdf]
    SoCG 2017.

  • Yossi Azar, Arun Ganesh, Rong Ge, Debmalya Panigrahi.
    Online Service with Delay. [    pdf]
    STOC 2017.

  • Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, Debmalya Panigrahi.
    Online and Dynamic Algorithms for Set Cover. [    pdf]
    STOC 2017.

  • Yuan Deng, Debmalya Panigrahi, Bo Waggoner.
    The Complexity of Stable Matchings under Substitutable Preferences. [    pdf]
    AAAI 2017.

  • Mohsen Ghaffari, David R. Karger, Debmalya Panigrahi.
    Random Contractions and Sampling for Hypergraph and Hedge Connectivity. [    pdf]
    SODA 2017.

2016

  • Rupert Freeman, Samuel Haney, Debmalya Panigrahi.
    On the Price of Stability of Multicast Games. [    pdf]
    WINE 2016.

  • Yossi Azar, Niv Buchbinder, T-H. Hubert Chan, Shahar Chen, Ilan Cohen, Anupam Gupta, Zhiyi Huang, Ning Kang, Viswanath Nagarajan, Joseph (Seffi) Naor, Debmalya Panigrahi.
    Online Algorithms for Covering and Packing Problems with Convex Objectives. [    pdf]
    FOCS 2016.

  • Nathaniel Kell, Debmalya Panigrahi.
    Online Budgeted Allocation with General Budgets. [    pdf]
    EC 2016.

  • Debmalya Panigrahi.
    Gomory-Hu Trees (survey). [pdf]
    Encyclopedia of Algorithms 2016.

  • Debmalya Panigrahi.
    Online Node-weighted Network Design (survey). [pdf]
    Encyclopedia of Algorithms 2016.

2015

  • Sungjin Im, Nathaniel Kell, Janardhan Kulkarni, Debmalya Panigrahi.
    Tight Bounds for Online Vector Scheduling. [    pdf]
    FOCS 2015.

  • Deeparnab Chakrabarty, Alina Ene, Ravishankar Krishnaswamy, Debmalya Panigrahi.
    Online Buy-at-Bulk Network Design. [    pdf]
    FOCS 2015.

  • Yossi Azar, Nikhil Devanur, Zhiyi Huang, Debmalya Panigrahi.
    Speed Scaling in the Non-clairvoyant Model. [    pdf]
    SPAA 2015.
    Best paper award.

2014

  • Sreenivas Gollapudi, Debmalya Panigrahi.
    Fair Allocation in Online Markets. [    pdf]
    CIKM 2014.

  • Kshipra Bhawalkar, Sreenivas Gollapudi, Debmalya Panigrahi.
    Online Set Cover with Set Requests. [    pdf]
    APPROX 2014.

  • Konstantin Makarychev, Debmalya Panigrahi.
    Precedence-constrained Scheduling of Malleable Jobs with Preemption. [    pdf]
    ICALP 2014.

  • MohammadTaghi Hajiaghayi, Vahid Liaghat, Debmalya Panigrahi.
    Near-optimal Online Algorithms for Prize-collecting Steiner Problems. [    pdf]
    ICALP 2014.

2013

  • MohammadTaghi Hajiaghayi, Vahid Liaghat, Debmalya Panigrahi.
    Online Node-weighted Steiner Forest and Extensions via Disk Paintings. [    pdf]
    FOCS 2013.
    SIAM Journal on Computing 46(3).

  • Debmalya Panigrahi, Sreenivas Gollapudi.
    Document Selection for Tiered Indexing in Commerce Search. [    pdf]
    WSDM 2013.

  • Yossi Azar, Umang Bhaskar, Lisa Fleischer, Debmalya Panigrahi.
    Online Mixed Packing and Covering. [    pdf]
    SODA 2013.

2012

  • Aranyak Mehta, Debmalya Panigrahi.
    Online Matching with Stochastic Rewards. [    pdf, ppt]
    FOCS 2012.

  • Debmalya Panigrahi, Atish Das Sarma, Gagan Aggarwal, Andrew Tomkins.
    Online Selection of Diverse Results. [    pdf, ppt]
    WSDM 2012.

2011

  • Aleksander Mądry, Debmalya Panigrahi.
    The Semi-stochastic Ski-rental Problem. [    pdf]
    FSTTCS 2011.

  • Joseph (Seffi) Naor, Debmalya Panigrahi, Mohit Singh.
    Online Node-weighted Steiner Tree and Related Problems. [    pdf, ppt]
    FOCS 2011.

  • Susan B. Davidson, Sanjeev Khanna, Tova Milo, Debmalya Panigrahi, Sudeepa Roy.
    Provenance Views for Module Privacy. [    pdf]
    PODS 2011.

  • Wai Shing Fung, Ramesh Hariharan, Nicholas J. A. Harvey, Debmalya Panigrahi.
    A General Framework for Graph Sparsification. [    pdf, ppt]
    STOC 2011.

  • Debmalya Panigrahi, Sreenivas Gollapudi.
    Result Enrichment in Commerce Search using Browse Trails. [    pdf, ppt]
    WSDM 2011.

  • Debmalya Panigrahi.
    Survivable Network Design Problems in Wireless Networks. [    pdf, ppt]
    SODA 2011.

2010

  • John R. Douceur, James Mickens, Thomas Moscibroda, Debmalya Panigrahi.
    Collaborative Measurements of Upload Speeds in P2P Systems. [    pdf, ppt]
    INFOCOM 2010.
    Brief Announcement in     PODC 2009.

  • Partha Dutta, Vivek Mhatre, Debmalya Panigrahi, Rajeev Rastogi.
    Joint Routing and Scheduling in Wireless Mesh Networks with Directional Antennas. [    pdf, ppt]
    INFOCOM 2010 (mini-conference).

2009

  • John R. Douceur, James Mickens, Thomas Moscibroda, Debmalya Panigrahi.
    ThunderDome: Discovering Upload Constraints Using Decentralized Bandwidth Tournaments. [    pdf]
    CoNEXT 2009.

  • Yossi Azar, Aleksander Mądry, Thomas Moscibroda, Debmalya Panigrahi, Aravind Srinivasan.
    Maximum Bipartite Flow in Networks with Adaptive Channel Width. [    pdf, ppt]
    ICALP 2009.
    Theoretical Computer Science 412(24) (Special issue for ICALP 2009).

  • Debmalya Panigrahi, Bhaskaran Raman.
    TDMA Scheduling in Long-Distance WiFi Networks. [    pdf]
    INFOCOM 2009 (mini-conference).

  • David R. Karger, Debmalya Panigrahi.
    A Near-Linear Time Algorithm for Constructing a Cactus Representation of Minimum Cuts. [    pdf, ppt]
    SODA 2009.

2008

  • Debmalya Panigrahi, Partha Dutta, Sharad Jaiswal, K V M Naidu, Rajeev Rastogi.
    Minimum Cost Topology Construction for Rural Wireless Mesh Networks. [    pdf]
    INFOCOM 2008.

  • K V M Naidu, Debmalya Panigrahi, Rajeev Rastogi.
    Detecting Anomalies Using End-to-End Path Measurements. [    pdf]
    INFOCOM 2008 (mini-conference).

  • Partha Dutta, Sharad Jaiswal, Debmalya Panigrahi, Rajeev Rastogi.
    A New Channel Assignment Mechanism for Rural Wireless Mesh Networks. [    pdf]
    INFOCOM 2008 (mini-conference).

  • Anand Bhalgat, Ramesh Hariharan, Telikepalli Kavitha, Debmalya Panigrahi.
    Fast Edge Splitting and Edmonds' Arborescence Construction for Unweighted Graphs. [    pdf, ppt]
    SODA 2008.

2007

  • Anand Bhalgat, Ramesh Hariharan, Telikepalli Kavitha, Debmalya Panigrahi.
    An Õ(mn) Gomory-Hu tree construction algorithm for unweighted graphs. [    pdf, ppt]
    STOC 2007.

  • Ramesh Hariharan, Telikepalli Kavitha, Debmalya Panigrahi.
    Efficient Algorithms for Computing All Low s-t Edge Connectivities and Related Problems. [    pdf, ppt]
    SODA 2007.

  • Partha Dutta, Sharad Jaiswal, K V M Naidu, Debmalya Panigrahi, Rajeev Rastogi, Ajay Todimala.
    VillageNet: A low-cost, 802.11-based mesh network for rural regions. [    pdf]
    WISARD 2007. (A workshop held in conjunction with COMSWARE 2007.)
    Best paper award.