DPDebmalya Panigrahi
Debmalya Panigrahi
*This is an algorithmically generated author record based on publicly available information.
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Debmalya Panigrahi has a total of 106 co-authors. Here are the top co-authors by number of shared publications:
- Amit Kumar
IIT Delhi, New Delhi, India
4 shared publications - Danupon Nanongkai
MPI-INF Germany
4 shared publications - Jason Li
Carnegie Mellon University, Pittsburgh, USA
4 shared publications - Jason Li
Carnegie Mellon University
4 shared publications - Ruoxu Cen
Department of Computer Science Duke University
4 shared publications Bruce M. Maggs
Department of Computer Science Duke University and Emerald Innovations
3 shared publications
Latest Publications
- Open Access
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 910-921
Fully Dynamic Set Cover: Worst-Case Recourse and Update Time
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 910-921
Open AccessFully Dynamic Set Cover: Worst-Case Recourse and Update Time
- Open Access
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1995-2006
Combinatorial Optimization using Comparison Oracles
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1995-2006
Open AccessCombinatorial Optimization using Comparison Oracles
- Open Access
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1548-1557
An Optimal Algorithm for Stochastic Vertex Cover
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1548-1557
Open AccessAn Optimal Algorithm for Stochastic Vertex Cover
- Open Access
Complexity of Local Search for CSPs Parameterized by Constraint Difference
In this paper, we study the parameterized complexity of local search, whose goal is to find a good nearby solution from the given current solution. Formally, given an optimization problem where the goal is to find the largest feasible subset $S$ of a universe $U$, the new input consists of a current solution $P$ (not necessarily feasible) as well as an ordinary input for the problem. Given the existence of a feasible solution $S^*$, the goal is to find a feasible solution as good as $S^*$ in parameterized time $f(k) \cdot n^{O(1)}$, where $k$ denotes the distance $|PΔS^*|$. This model generalizes numerous classical parameterized optimization problems whose parameter $k$ is the minimum number of elements removed from $U$ to make it feasible, which corresponds to the case $P = U$. We apply this model to widely studied Constraint Satisfaction Problems (CSPs), where $U$ is the set of constraints, and a subset $U'$ of constraints is feasible if there is an assignment to the variables satisfying all constraints in $U'$. We give a complete characterization of the parameterized complexity of all boolean-alphabet symmetric CSPs, where the predicate's acceptance depends on the number of true literals.Open AccessComplexity of Local Search for CSPs Parameterized by Constraint Difference
In this paper, we study the parameterized complexity of local search, whose goal is to find a good nearby solution from the given current solution. Formally, given an optimization problem where the goal is to find the largest feasible subset $S$ of a universe $U$, the new input consists of a current solution $P$ (not necessarily feasible) as well as an ordinary input for the problem. Given the existence of a feasible solution $S^*$, the goal is to find a feasible solution as good as $S^*$ in parameterized time $f(k) \cdot n^{O(1)}$, where $k$ denotes the distance $|PΔS^*|$. This model generalizes numerous classical parameterized optimization problems whose parameter $k$ is the minimum number of elements removed from $U$ to make it feasible, which corresponds to the case $P = U$. We apply this model to widely studied Constraint Satisfaction Problems (CSPs), where $U$ is the set of constraints, and a subset $U'$ of constraints is feasible if there is an assignment to the variables satisfying all constraints in $U'$. We give a complete characterization of the parameterized complexity of all boolean-alphabet symmetric CSPs, where the predicate's acceptance depends on the number of true literals. - Open Access
Fully Dynamic Set Cover: Worst-Case Recourse and Update Time
In (fully) dynamic set cover, the goal is to maintain an approximately optimal solution to a dynamically evolving instance of set cover, where in each step either an element is added to or removed from the instance. The two main desiderata of a dynamic set cover algorithm are to minimize at each time-step, the recourse, which is the number of sets removed from or added to the solution, and the update time to compute the updated solution. This problem has been extensively studied over the last decade leading to many results that achieve ever-improving bounds on the recourse and update time, while maintaining a solution whose cost is comparable to that of offline approximation algorithms. In this paper, we give the first algorithms to simultaneously achieve non-trivial worst-case bounds for recourse and update time. Specifically, we give fully-dynamic set cover algorithms that simultaneously achieve $O(\log n)$ recourse and $f\cdot \textrm{poly}\log(n)$ update time in the worst-case, for both approximation regimes: $O(\log n)$ and $O(f)$ approximation. (Here, $n, f$ respectively denote the maximum number of elements and maximum frequency of an element across all instances.) Prior to our work, all results for this problem either settled for amortized bounds on recourse and update time, or obtained $f\cdot \textrm{poly}\log(n)$ update time in the worst-case but at the cost of $Ω(m)$ worst-case recourse. (Here, $m$ denotes the number of sets. Note that any algorithm has recourse at most $m$.)Open AccessFully Dynamic Set Cover: Worst-Case Recourse and Update Time
In (fully) dynamic set cover, the goal is to maintain an approximately optimal solution to a dynamically evolving instance of set cover, where in each step either an element is added to or removed from the instance. The two main desiderata of a dynamic set cover algorithm are to minimize at each time-step, the recourse, which is the number of sets removed from or added to the solution, and the update time to compute the updated solution. This problem has been extensively studied over the last decade leading to many results that achieve ever-improving bounds on the recourse and update time, while maintaining a solution whose cost is comparable to that of offline approximation algorithms. In this paper, we give the first algorithms to simultaneously achieve non-trivial worst-case bounds for recourse and update time. Specifically, we give fully-dynamic set cover algorithms that simultaneously achieve $O(\log n)$ recourse and $f\cdot \textrm{poly}\log(n)$ update time in the worst-case, for both approximation regimes: $O(\log n)$ and $O(f)$ approximation. (Here, $n, f$ respectively denote the maximum number of elements and maximum frequency of an element across all instances.) Prior to our work, all results for this problem either settled for amortized bounds on recourse and update time, or obtained $f\cdot \textrm{poly}\log(n)$ update time in the worst-case but at the cost of $Ω(m)$ worst-case recourse. (Here, $m$ denotes the number of sets. Note that any algorithm has recourse at most $m$.) - Open Access
Nearly Tight Bounds for the Online Sorting Problem
In the online sorting problem, a sequence of $n$ numbers in $[0, 1]$ (including $\{0,1\}$) have to be inserted in an array of size $m \ge n$ so as to minimize the sum of absolute differences between pairs of numbers occupying consecutive non-empty cells. Previously, Aamand {\em et al.} (SODA 2023) gave a deterministic $2^{\sqrt{\log n} \sqrt{\log \log n + \log (1/\varepsilon)}}$-competitive algorithm when $m = (1+\varepsilon) n$ for any $\varepsilon \ge Ω(\log n/n)$. They also showed a lower bound: with $m = γn$ space, the competitive ratio of any deterministic algorithm is at least $\frac{1}γ\cdotΩ(\log n / \log \log n)$. This left an exponential gap between the upper and lower bounds for the problem. In this paper, we bridge this exponential gap and almost completely resolve the online sorting problem. First, we give a deterministic $O(\log^2 n / \varepsilon)$-competitive algorithm with $m = (1+\varepsilon) n$, for any $\varepsilon \ge Ω(\log n / n)$. Next, for $m = γn$ where $γ= [O(1), O(\log^2 n)]$, we give a deterministic $O(\log^2 n / γ)$-competitive algorithm. In particular, this implies an $O(1)$-competitive algorithm with $O(n \log^2 n)$ space, which is within an $O(\log n\cdot \log \log n)$ factor of the lower bound of $Ω(n \log n / \log \log n)$. Combined, the two results imply a close to optimal tradeoff between space and competitive ratio for the entire range of interest: specifically, an upper bound of $O(\log^2 n)$ on the product of the competitive ratio and $γ$ while the lower bound on this product is $Ω(\log n / \log\log n)$. We also show that these results can be extended to the case when the range of the numbers is not known in advance, for an additional $O(\log n)$ factor in the competitive ratio.Open AccessNearly Tight Bounds for the Online Sorting Problem
In the online sorting problem, a sequence of $n$ numbers in $[0, 1]$ (including $\{0,1\}$) have to be inserted in an array of size $m \ge n$ so as to minimize the sum of absolute differences between pairs of numbers occupying consecutive non-empty cells. Previously, Aamand {\em et al.} (SODA 2023) gave a deterministic $2^{\sqrt{\log n} \sqrt{\log \log n + \log (1/\varepsilon)}}$-competitive algorithm when $m = (1+\varepsilon) n$ for any $\varepsilon \ge Ω(\log n/n)$. They also showed a lower bound: with $m = γn$ space, the competitive ratio of any deterministic algorithm is at least $\frac{1}γ\cdotΩ(\log n / \log \log n)$. This left an exponential gap between the upper and lower bounds for the problem. In this paper, we bridge this exponential gap and almost completely resolve the online sorting problem. First, we give a deterministic $O(\log^2 n / \varepsilon)$-competitive algorithm with $m = (1+\varepsilon) n$, for any $\varepsilon \ge Ω(\log n / n)$. Next, for $m = γn$ where $γ= [O(1), O(\log^2 n)]$, we give a deterministic $O(\log^2 n / γ)$-competitive algorithm. In particular, this implies an $O(1)$-competitive algorithm with $O(n \log^2 n)$ space, which is within an $O(\log n\cdot \log \log n)$ factor of the lower bound of $Ω(n \log n / \log \log n)$. Combined, the two results imply a close to optimal tradeoff between space and competitive ratio for the entire range of interest: specifically, an upper bound of $O(\log^2 n)$ on the product of the competitive ratio and $γ$ while the lower bound on this product is $Ω(\log n / \log\log n)$. We also show that these results can be extended to the case when the range of the numbers is not known in advance, for an additional $O(\log n)$ factor in the competitive ratio. - Open Access
Deterministic Almost-Linear-Time Gomory-Hu Trees
Given an $m$-edge, undirected, weighted graph $G=(V,E,w)$, a Gomory-Hu tree $T$ (Gomory and Hu, 1961) is a tree over the vertex set $V$ such that all-pairs mincuts in $G$ are preserved exactly in $T$. In this article, we give the first almost-optimal $m^{1+o(1)}$-time deterministic algorithm for constructing a Gomory-Hu tree. Prior to our work, the best deterministic algorithm for this problem dated back to the original algorithm of Gomory and Hu that runs in $nm^{1+o(1)}$ time (using current maxflow algorithms). In fact, this is the first almost-linear time deterministic algorithm for even simpler problems, such as finding the $k$-edge-connected components of a graph. Our new result hinges on two separate and novel components that each introduce a distinct set of de-randomization tools of independent interest: - a deterministic reduction from the all-pairs mincuts problem to the single-souce mincuts problem incurring only subpolynomial overhead, and - a deterministic almost-linear time algorithm for the single-source mincuts problem.Open AccessDeterministic Almost-Linear-Time Gomory-Hu Trees
Given an $m$-edge, undirected, weighted graph $G=(V,E,w)$, a Gomory-Hu tree $T$ (Gomory and Hu, 1961) is a tree over the vertex set $V$ such that all-pairs mincuts in $G$ are preserved exactly in $T$. In this article, we give the first almost-optimal $m^{1+o(1)}$-time deterministic algorithm for constructing a Gomory-Hu tree. Prior to our work, the best deterministic algorithm for this problem dated back to the original algorithm of Gomory and Hu that runs in $nm^{1+o(1)}$ time (using current maxflow algorithms). In fact, this is the first almost-linear time deterministic algorithm for even simpler problems, such as finding the $k$-edge-connected components of a graph. Our new result hinges on two separate and novel components that each introduce a distinct set of de-randomization tools of independent interest: - a deterministic reduction from the all-pairs mincuts problem to the single-souce mincuts problem incurring only subpolynomial overhead, and - a deterministic almost-linear time algorithm for the single-source mincuts problem. - Open Access
- 24 July 2025
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 72 (4) , 1-18
Deterministic Minimum Cut in Poly-logarithmic Maximum Flows
We give a deterministic algorithm for finding the minimum (weight) cut of an undirected graph on n vertices and m edges using polylog ( n ) calls to a black box maximum flow subroutine. Using the current best deterministic maximum flow algorithms, this marks the first improvement for this problem since a running time bound of \(\tilde{O}(mn)\) was established by several papers in the early 1990s. Our global minimum cut algorithm is obtained as a corollary of a deterministic minimum Steiner cut algorithm, where a minimum Steiner cut is a minimum (weight) set of edges whose removal disconnects at least one pair of vertices among a designated set of terminal vertices. We also give a remarkably simple randomized minimum Steiner cut algorithm that still improves the best known randomized algorithm for the problem. Our main technical contribution is a new tool that we call isolating cuts . Given a set of vertices R , this entails finding cuts of minimum weight that separate (or isolate) each individual vertex \(v\in R\) from the rest of the vertices \(R\setminus \lbrace v\rbrace\) . Naïvely, this can be done using |R| maximum flow calls, but we show that just O (log |R| ) calls on graphs containing O(n) vertices and O(m) edges suffice. We call this the isolating cut lemma .- 24 July 2025
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 72 (4) , 1-18
Open AccessDeterministic Minimum Cut in Poly-logarithmic Maximum Flows
We give a deterministic algorithm for finding the minimum (weight) cut of an undirected graph on n vertices and m edges using polylog ( n ) calls to a black box maximum flow subroutine. Using the current best deterministic maximum flow algorithms, this marks the first improvement for this problem since a running time bound of \(\tilde{O}(mn)\) was established by several papers in the early 1990s. Our global minimum cut algorithm is obtained as a corollary of a deterministic minimum Steiner cut algorithm, where a minimum Steiner cut is a minimum (weight) set of edges whose removal disconnects at least one pair of vertices among a designated set of terminal vertices. We also give a remarkably simple randomized minimum Steiner cut algorithm that still improves the best known randomized algorithm for the problem. Our main technical contribution is a new tool that we call isolating cuts . Given a set of vertices R , this entails finding cuts of minimum weight that separate (or isolate) each individual vertex \(v\in R\) from the rest of the vertices \(R\setminus \lbrace v\rbrace\) . Naïvely, this can be done using |R| maximum flow calls, but we show that just O (log |R| ) calls on graphs containing O(n) vertices and O(m) edges suffice. We call this the isolating cut lemma . - Open Access
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 120-131
Network Unreliability in Almost-Linear Time
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 120-131
Open AccessNetwork Unreliability in Almost-Linear Time
- Open Access
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 1418-1429
Tight Results for Online Convex Paging
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 1418-1429
Open AccessTight Results for Online Convex Paging