Publications

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

Graph Algorithms

Ruoxu Cen, Jason Li, Debmalya Panigrahi.
Hypergraph Unreliability in Quasi-Polynomial Time.
STOC 2024.
Ruoxu Cen, William He, Jason Li, Debmalya Panigrahi.
Beyond the Quadratic Time Barrier for Network Unreliability.
SODA 2024.
Amir Abboud, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak.
All-Pairs Max-Flow is no Harder than Single-Pair Max-Flow: Gomory-Hu Trees in Almost-Linear Time.
FOCS 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.
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.
Ruoxu Cen, Jason Li, Debmalya Panigrahi.
Edge-Connectivity Augmentation in Near-Linear Time. [pdf]
STOC 2022.
Ruoxu Cen, Jason Li, Debmalya Panigrahi.
Augmenting Edge Connectivity via Isolating Cuts. [pdf]
SODA 2022.
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 Graphs via Partial Sparsification. [pdf]
FOCS 2021.
Ruoxu Cen, Yu Cheng, Debmalya Panigrahi, and Kevin Sun.
Sparsification of Directed Graphs via Cut Balance. [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.
Jason Li, Debmalya Panigrahi.
Deterministic Min-cut in Poly-logarithmic Max-flows. [pdf]
FOCS 2020.
Arun Ganesh, Bruce Maggs, Debmalya Panigrahi.
Robust Algorithms for TSP and Steiner Tree. [pdf]
ICALP 2020.
Samuel Haney, Mehraneh Liaee, Bruce M. Maggs, Debmalya Panigrahi, Rajmohan Rajaraman, Ravi Sundaram.
Retracting Graphs to Cycles. [pdf]
ICALP 2019.
Kyle Fox, Debmalya Panigrahi, Fred Zhang.
Minimum Cut and Minimum k-Cut in Hypergraphs via Branching Contractions. [pdf]
SODA 2019.
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.
Mohsen Ghaffari, David R. Karger, Debmalya Panigrahi.
Random Contractions and Sampling for Hypergraph and Hedge Connectivity. [pdf]
SODA 2017.
Debmalya Panigrahi.
Gomory-Hu Trees (survey). [pdf]
Encyclopedia of Algorithms 2016.
Debmalya Panigrahi.
Online Node-weighted Network Design (survey). [pdf]
Encyclopedia of Algorithms 2016.
Deeparnab Chakrabarty, Alina Ene, Ravishankar Krishnaswamy, Debmalya Panigrahi.
Online Buy-at-Bulk Network Design. [pdf]
FOCS 2015.
MohammadTaghi Hajiaghayi, Vahid Liaghat, Debmalya Panigrahi.
Near-optimal Online Algorithms for Prize-collecting Steiner Problems. [pdf]
ICALP 2014.
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).
Joseph (Seffi) Naor, Debmalya Panigrahi, Mohit Singh.
Online Node-weighted Steiner Tree and Related Problems. [pdf, ppt]
FOCS 2011.
Wai Shing Fung, Ramesh Hariharan, Nicholas J. A. Harvey, Debmalya Panigrahi.
A General Framework for Graph Sparsification. [pdf, ppt]
STOC 2011.
Debmalya Panigrahi.
Survivable Network Design Problems in Wireless Networks. [pdf, ppt]
SODA 2011.
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).
David R. Karger, Debmalya Panigrahi.
A Near-Linear Time Algorithm for Constructing a Cactus Representation of Minimum Cuts. [pdf, ppt]
SODA 2009.
Anand Bhalgat, Ramesh Hariharan, Telikepalli Kavitha, Debmalya Panigrahi.
Fast Edge Splitting and Edmonds' Arborescence Construction for Unweighted Graphs. [pdf, ppt]
SODA 2008.
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.

online algorithms

Anupam Gupta, Amit Kumar, Debmalya Panigrahi.
Poly-logarithmic Competitiveness or the k-Taxi Problem.
SODA 2024.
Anupam Gupta, Amit Kumar, Debmalya Panigrahi.
Efficient Algorithms and Hardness Results for the Weighted k-server Problem.
APPROX 2023.
Marek Chrobak, Samuel Haney, Mehraneh Liaee, Debmalya Panigrahi, Rajmohan Rajaraman, Ravi Sundaram, Neal E. Young.
Online Paging with Heterogeneous Cache Slots.
STACS 2023.
Anupam Gupta, Amit Kumar, Debmalya Panigrahi.
A Hitting Set Relaxation for k-Server and an Extension to Time Windows. [pdf]
FOCS 2021.
Arun Ganesh, Bruce Maggs, and Debmalya Panigrahi.
Universal Algorithms for Clustering Problems. [pdf]
ICALP 2021.
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.
Amir Abboud, Raghavendra Addanki, Fabrizio Grandoni, Debmalya Panigrahi, Barna Saha.
Dynamic Set Cover: Improved Algorithms and Lower Bounds. [pdf]
STOC 2019.
Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, Debmalya Panigrahi.
Elastic Caching. [pdf]
SODA 2019.
Sungjin Im, Nathaniel Kell, Debmalya Panigrahi, Maryam Shadloo.
Online Load Balancing on Related Machines. [pdf]
STOC 2018.
Yossi Azar, Ilan Cohen, Debmalya Panigrahi.
Randomized Algorithms for Online Vector Load Balancing. [pdf]
SODA 2018.
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.
STOC 2017. [pdf]
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.
Sungjin Im, Nathaniel Kell, Janardhan Kulkarni, Debmalya Panigrahi.
Tight Bounds for Online Vector Scheduling. [pdf]
FOCS 2015.
Yossi Azar, Nikhil Devanur, Zhiyi Huang, Debmalya Panigrahi.
Speed Scaling in the Non-clairvoyant Model. [pdf]
SPAA 2015.
Best paper award.
Kshipra Bhawalkar, Sreenivas Gollapudi, Debmalya Panigrahi.
Online Set Cover with Set Requests. [pdf]
APPROX 2014.
Yossi Azar, Umang Bhaskar, Lisa Fleischer, Debmalya Panigrahi.
Online Mixed Packing and Covering. [pdf]
SODA 2013.
Aleksander Mądry, Debmalya Panigrahi.
The Semi-stochastic Ski-rental Problem. [pdf]
FSTTCS 2011.

machine learning

Yossi Azar, Debmalya Panigrahi, Noam Touitou.
Discrete-Smoothness in Online Algorithms with Predictions.
NeurIPS 2023.
Ilan Cohen, Debmalya Panigrahi.
A General Framework for Learning-Augmented Online Allocation.
ICALP 2023.
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.
Keerti Anand, Rong Ge, Amit Kumar, Debmalya Panigrahi.
Online Algorithms with Multiple Predictions. [pdf]
ICML 2022.
Vincent Conitzer, Debmalya Panigrahi, Hanrui Zhang.
Learning Influence Adoption in Heterogeneous Networks.
AAAI 2022.
Yossi Azar, Debmalya Panigrahi, Noam Touitou.
Online Graph Algorithms with Predictions. [pdf]
SODA 2022.
Keerti Anand, Rong Ge, Amit Kumar, Debmalya Panigrahi.
A Regression Approach to Learning-Augmented Online Algorithms. [pdf]
NeurIPS 2021.
Keerti Anand, Rong Ge, Debmalya Panigrahi.
Customizing ML Predictions for Online Algorithms. [pdf]
ICML 2020.
Vincent Conitzer, Debmalya Panigrahi, Hanrui Zhang.
Learning Opinions in Social Networks. [pdf]
ICML 2020.
Zhihao Jiang, Debmalya Panigrahi, Kevin Sun.
Online Algorithms for Weighted Paging with Predictions. [pdf]
ICALP 2020.
Sreenivas Gollapudi, Debmalya Panigrahi.
Online Algorithms for Rent-Or-Buy with Expert Advice. [pdf]
ICML 2019.

computational economics

Yuan Deng, Debmalya Panigrahi, and Hanrui Zhang.
Online Combinatorial Auctions.
SODA 2021. [pdf]
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.
Shuchi Chawla, Joseph (Seffi) Naor, Debmalya Panigrahi, Mohit Singh, Seeun Umboh.
Timing Matters: Online Dynamics in Broadcast Games. [pdf]
WINE 2018.
Sreenivas Gollapudi, Kostas Kollias, Debmalya Panigrahi, Venetia Pliatsika.
Profit Sharing and Efficiency in Utility Games. [pdf]
ESA 2017.
Yuan Deng, Debmalya Panigrahi, Bo Waggoner.
The Complexity of Stable Matchings under Substitutable Preferences. [pdf]
AAAI 2017.
Rupert Freeman, Samuel Haney, Debmalya Panigrahi.
On the Price of Stability of Multicast Games. [pdf]
WINE 2016.
Nathaniel Kell, Debmalya Panigrahi.
Online Budgeted Allocation with General Budgets. [pdf]
EC 2016.
Sreenivas Gollapudi, Debmalya Panigrahi.
Fair Allocation in Online Markets. [pdf]
CIKM 2014.
Aranyak Mehta, Debmalya Panigrahi.
Online Matching with Stochastic Rewards. [pdf, ppt]
FOCS 2012.

Internet algorithms

Sreenivas Gollapudi, Kostas Kollias, Debmalya Panigrahi.
The Pit-Stop Problem: How to Plan Your Next Road Trip. [pdf]
SIGSPATIAL 2022.
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
Sreenivas Gollapudi, Ravi Kumar, Debmalya Panigrahi, Rina Panigrahy.
Partitioning Orders in Online Shopping Services. [pdf]
CIKM 2017.
Konstantin Makarychev, Debmalya Panigrahi.
Precedence-constrained Scheduling of Malleable Jobs with Preemption. [pdf]
ICALP 2014.
Debmalya Panigrahi, Sreenivas Gollapudi.
Document Selection for Tiered Indexing in Commerce Search. [pdf]
WSDM 2013.
Debmalya Panigrahi, Atish Das Sarma, Gagan Aggarwal, Andrew Tomkins.
Online Selection of Diverse Results. [pdf, ppt]
WSDM 2012.
Debmalya Panigrahi, Sreenivas Gollapudi.
Result Enrichment in Commerce Search using Browse Trails. [pdf, ppt]
WSDM 2011.

databases

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.
Xiao Hu, Shouzhuo Sun, Shweta Patwa, Debmalya Panigrahi, and Sudeepa Roy.
Aggregated Deletion Propagation for Counting Conjunctive Query Answers. [pdf]
VLDB 2021.
Susan B. Davidson, Sanjeev Khanna, Tova Milo, Debmalya Panigrahi, Sudeepa Roy.
Provenance Views for Module Privacy. [pdf]
PODS 2011.

networks

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).
John R. Douceur, James Mickens, Thomas Moscibroda, Debmalya Panigrahi.
ThunderDome: Discovering Upload Constraints Using Decentralized Bandwidth Tournaments. [pdf]
CoNEXT 2009.
Debmalya Panigrahi, Bhaskaran Raman.
TDMA Scheduling in Long-Distance WiFi Networks. [pdf]
INFOCOM 2009 (mini-conference).
Debmalya Panigrahi, Partha Dutta, Sharad Jaiswal, K V M Naidu, Rajeev Rastogi.
Minimum Cost Topology Construction for Rural Wireless Mesh Networks. [pdf]
INFOCOM 2008.
Partha Dutta, Sharad Jaiswal, Debmalya Panigrahi, Rajeev Rastogi.
A New Channel Assignment Mechanism for Rural Wireless Mesh Networks. [pdf]
INFOCOM 2008 (mini-conference).
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, 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.