Deeparnab Chakrabarty

STOC Conference 2025 Conference Paper

Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning

• Deeparnab Chakrabarty
• Xi Chen 0001
• Simeon Ristic
• C. Seshadhri 0001
• Erik Waingarten

We study monotonicity testing of high-dimensional distributions on {−1,1} n in the model of subcube conditioning, suggested and studied by Canonne, Ron, and Servedio and Bhattacharyya and Chakraborty. Previous work shows that the sample complexity of monotonicity testing must be exponential in n (Rubinfeld, Vasilian, and Aliakbarpour, Gouleakis, Peebles, Rubinfeld, Yodpinyanee). We show that the subcube query complexity is Θ( n /є 2 ), by proving nearly matching upper and lower bounds. Our work is the first to use directed isoperimetric inequalities (developed for function monotonicity testing) for analyzing a distribution testing algorithm. Along the way, we generalize an inequality of Khot, Minzer, and Safra to real-valued functions on {−1,1} n . We also study uniformity testing of distributions that are promised to be monotone, a problem introduced by Rubinfeld, Servedio, using subcube conditioning. We show that the query complexity is Θ(√ n /є 2 ). Our work proves the lower bound, which matches (up to poly-logarithmic factors) the uniformity testing upper bound for general distributions (Canonne, Chen, Kamath, Levi, Waingarten). Hence, we show that monotonicity does not help, beyond logarithmic factors, in testing uniformity of distributions with subcube conditional queries.

FOCS Conference 2023 Conference Paper

A d 1/2+o(1) Monotonicity Tester for Boolean Functions on d-Dimensional Hypergrids

• Hadley Black
• Deeparnab Chakrabarty
• C. Seshadhri 0001

Monotonicity testing of Boolean functions on the hypergrid, $f: [n]^{d} \rightarrow\{0, 1\}$, is a classic topic in property testing. Determining the non-adaptive complexity of this problem is an important open question. For arbitrary n, [Black-Chakrabarty-Seshadhri, SODA 2020] describe a tester with query complexity $\widetilde{O}\left(\varepsilon^{-4 / 3} d^{5 / 6}\right)$. This complexity is independent of n, but has a suboptimal dependence on d. Recently, [Braverman-Khot-Kindler-Minzer, ITCS 2023] and [Black-Chakrabarty-Seshadhri, STOC 2023] describe $\widetilde{O}\left(\varepsilon^{-2} n^{3} \sqrt{d}\right)$ and $\widetilde{O}\left(\varepsilon^{-2} n \sqrt{d}\right)$-query testers, respectively. These testers have an almost optimal dependence on d, but a suboptimal polynomial dependence on n. In this paper, we describe a non-adaptive, onesided monotonicity tester with query complexity $O\left(\varepsilon^{-2} d^{1 / 2+o(1)}\right)$, independent of n. Up to the $d^{o(1)}$. factors, our result resolves the non-adaptive complexity of monotonicity testing for Boolean functions on hypergrids. The independence of n yields a non-adaptive, one-sided $O\left(\varepsilon^{-2} d^{1 / 2+o(1)}\right)$-query monotonicity tester for Boolean functions $f: \mathbb{R}^{d} \rightarrow\{0, 1\}$ associated with an arbitrary product measure.

STOC Conference 2023 Conference Paper

Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an Õ(n√d) Monotonicity Tester

• Hadley Black
• Deeparnab Chakrabarty
• C. Seshadhri 0001

NeurIPS Conference 2023 Conference Paper

Parallel Submodular Function Minimization

• Deeparnab Chakrabarty
• Andrei Graur
• Haotian Jiang
• Aaron Sidford

We consider the parallel complexity of submodular function minimization (SFM). We provide a pair of methods which obtain two new query versus depth trade-offs a submodular function defined on subsets of $n$ elements that has integer values between $-M$ and $M$. The first method has depth $2$ and query complexity $n^{O(M)}$ and the second method has depth $\widetilde{O}(n^{1/3} M^{2/3})$ and query complexity $O(\mathrm{poly}(n, M))$. Despite a line of work on improved parallel lower bounds for SFM, prior to our work the only known algorithms for parallel SFM either followed from more general methods for sequential SFM or highly-parallel minimization of convex $\ell_2$-Lipschitz functions. Interestingly, to obtain our second result we provide the first highly-parallel algorithm for minimizing $\ell_\infty$-Lipschitz function over the hypercube which obtains near-optimal depth for obtaining constant accuracy.

FOCS Conference 2022 Conference Paper

Improved Lower Bounds for Submodular Function Minimization

• Deeparnab Chakrabarty
• Andrei Graur
• Haotian Jiang
• Aaron Sidford

We provide a generic technique for constructing families of submodular functions to obtain lower bounds for submodular function minimization (SFM). Applying this technique, we prove that any deterministic SFM algorithm on a ground set of n elements requires at least $\Omega(n\log n)$ queries to an evaluation oracle. This is the first super-linear query complexity lower bound for SFM and improves upon the previous best lower bound of 2n given by [Graur et al. , ITCS 2020]. Using our construction, we also prove that any (possibly randomized) parallel SFM algorithm, which can make up to poly $(n)$ queries per round, requires at least $\Omega(n/\log n)$ rounds to minimize a submodular function. This improves upon the previous best lower bound of $\tilde{\Omega}(n^{1/3})$ rounds due to [Chakrabarty et al. , FOCS 2021], and settles the parallel complexity of query-efficient SFM up to logarithmic factors due to a recent advance in [Jiang, SODA 2021].

FOCS Conference 2021 Conference Paper

A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization

• Deeparnab Chakrabarty
• Yu Chen 0039
• Sanjeev Khanna

The problem of minimizing a submodular function (SFM) is a common generalization of several fundamental combinatorial optimization problems, including minimum $s-t$ cuts in graphs and matroid intersection. It is well-known that a submodular function can be minimized with only $\text{poly} (N)$ function evaluation queries where $N$ denotes the universe size. However, all known polynomial query algorithms for SFM are highly adaptive, requiring at least $N$ rounds of adaptivity. A natural question is if SFM can be efficiently solved in a highly parallel manner, namely, with $\text{poly} (N)$ queries using only poly-logarithmic rounds of adaptivity. An important step towards understanding the adaptivity needed to solve SFM efficiently was taken in the very recent work of Balkanski and Singer who showed that any SFM algorithm with $\text{poly} (N)$ queries. This left open the possibility of efficient SFM algorithms with poly-logarithmic rounds of adaptivity. In this work, we strongly rule out this possibility by showing that any, possibly randomized, algorithm for submodular function minimization making $\text{poly} (N)$ queries requires $\tilde{\Omega}(N^{1/3})$ rounds of adaptivity. In fact, we show a polynomial lower bound on the number of rounds of adaptivity even for algorithms that make up to $2^{N^{1-\delta}}$ queries, for any constant $\delta > 0$.

NeurIPS Conference 2021 Conference Paper

Better Algorithms for Individually Fair $k$-Clustering

• Maryam Negahbani
• Deeparnab Chakrabarty

We study data clustering problems with $\ell_p$-norm objectives (e. g. \textsc{$k$-Median} and \textsc{$k$-Means}) in the context of individual fairness. The dataset consists of $n$ points, and we want to find $k$ centers such that (a) the objective is minimized, while (b) respecting the individual fairness constraint that every point $v$ has a center within a distance at most $r(v)$, where $r(v)$ is $v$'s distance to its $(n/k)$th nearest point. Jung, Kannan, and Lutz [FORC 2020] introduced this concept and designed a clustering algorithm with provable (approximate) fairness and objective guarantees for the $\ell_\infty$ or \textsc{$k$-Center} objective. Mahabadi and Vakilian [ICML 2020] revisited this problem to give a local-search algorithm for all $\ell_p$-norms. Empirically, their algorithms outperform Jung et. al. 's by a large margin in terms of cost (for \textsc{$k$-Median} and \textsc{$k$-Means}), but they incur a reasonable loss in fairness. In this paper, our main contribution is to use Linear Programming (LP) techniques to obtain better algorithms for this problem, both in theory and in practice. We prove that by modifying known LP rounding techniques, one gets a worst-case guarantee on the objective which is much better than in MV20, and empirically, this objective is extremely close to the optimal. Furthermore, our theoretical fairness guarantees are comparable with MV20 in theory, and empirically, we obtain noticeably fairer solutions. Although solving the LP {\em exactly} might be prohibitive, we demonstrate that in practice, a simple sparsification technique drastically improves the run-time of our algorithm.

SODA Conference 2020 Conference Paper

Domain Reduction for Monotonicity Testing: A o ( d ) Tester for Boolean Functions in d -Dimensions

• Hadley Black
• Deeparnab Chakrabarty
• C. Seshadhri 0001

STOC Conference 2019 Conference Paper

Approximation algorithms for minimum norm and ordered optimization problems

• Deeparnab Chakrabarty
• Chaitanya Swamy

NeurIPS Conference 2019 Conference Paper

Fair Algorithms for Clustering

• Suman Bera
• Deeparnab Chakrabarty
• Nicolas Flores
• Maryam Negahbani

We study the problem of finding low-cost {\em fair clusterings} in data where each data point may belong to many protected groups. Our work significantly generalizes the seminal work of Chierichetti \etal (NIPS 2017) as follows. - We allow the user to specify the parameters that define fair representation. More precisely, these parameters define the maximum over- and minimum under-representation of any group in any cluster. - Our clustering algorithm works on any $\ell_p$-norm objective (e. g. $k$-means, $k$-median, and $k$-center). Indeed, our algorithm transforms any vanilla clustering solution into a fair one incurring only a slight loss in quality. - Our algorithm also allows individuals to lie in multiple protected groups. In other words, we do not need the protected groups to partition the data and we can maintain fairness across different groups simultaneously. Our experiments show that on established data sets, our algorithm performs much better in practice than what our theoretical results suggest.

FOCS Conference 2019 Conference Paper

Faster Matroid Intersection

• Deeparnab Chakrabarty
• Yin Tat Lee
• Aaron Sidford
• Sahil Singla 0001
• Sam Chiu-wai Wong

In this paper we consider the classic matroid intersection problem: given two matroids M 1 = (V, I 1 ) and M 2 = (V, I 2 ) defined over a common ground set V, compute a set S ∈ I 1 ∩ I 2 of largest possible cardinality, denoted by r. We consider this problem both in the setting where each Mi is accessed through an independence oracle, i. e. a routine which returns whether or not a set S ∈ I i in T ind time, and the setting where each Mi is accessed through a rank oracle, i. e. a routine which returns the size of the largest independent subset of S in M i in T rank time. In each setting we provide faster exact and approximate algorithms. Given an independence oracle, we provide an exact O(nr log r · T ind ) time algorithm. This improves upon previous best known running times of O(nr 1. 5 ·T ind ) due to Cunningham O(n 2 ·T ind in 1986 and + n 3 ) due to Lee, Sidford, and Wong in 2015. We also provide two algorithms which compute a (1- ε-approximate solution to matroid intersection running in times O(n 1. 5 /ε 1. 5 · Tind) and O((n 2 r -1 ε -2 + r 1. 5 ε -4. 5 ) · Tind), respectively. These results improve upon the O(nr/ε · T ind )time algorithm of Cunningham (noted recently by Chekuri and Quanrud). Given a rank oracle, we provide algorithms with even better dependence on n and r. We provide an O(n√r log n · T rank )time exact algorithm and an O(nε -1 log n · T rank )-time algorithm which obtains a (1 - 0)-approximation to the matroid intersection problem. The former result improves over the O(nr · T rank + n 3 )-time algorithm by Lee, Sidford, and Wong. The rank oracle is of particular interest as the matroid intersection problem with this oracle is a special case (via Edmond's minimax characterization of matroid intersection) of the submodular function minimization (SFM) problem with an evaluation oracle, and understanding SFM query complexity is an outstanding open question.

SODA Conference 2018 Conference Paper

A o ( d ) · polylog n Monotonicity Tester for Boolean Functions over the Hypergrid [ n ] d

• Hadley Black
• Deeparnab Chakrabarty
• C. Seshadhri 0001

We study monotonicity testing of Boolean functions over the hypergrid [ n ] d and design a non-adaptive tester with 1-sided error whose query complexity is Õ ( d 5/6 ). poly(log n, 1/ ε ). Previous to our work, the best known testers had query complexity linear in d but independent of n. We improve upon these testers as long as n = 2 d o (1). To obtain our results, we work with what we call the augmented hypergrid, which adds extra edges to the hypergrid. Our main technical contribution is a Margulis-style isoperimetric result for the augmented hypergrid, and our tester, like previous testers for the hypercube domain, performs directed random walks on this structure.

SODA Conference 2018 Conference Paper

Dynamic Algorithms for Graph Coloring

• Sayan Bhattacharya
• Deeparnab Chakrabarty
• Monika Henzinger
• Danupon Nanongkai

We design fast dynamic algorithms for proper vertex and edge colorings in a graph undergoing edge insertions and deletions. In the static setting, there are simple linear time algorithms for (Δ + 1)- vertex coloring and (2Δ – 1)-edge coloring in a graph with maximum degree Δ. It is natural to ask if we can efficiently maintain such colorings in the dynamic setting as well. We get the following three results. (1) We present a randomized algorithm which maintains a (Δ + 1)-vertex coloring with O (log Δ) expected amortized update time. (2) We present a deterministic algorithm which maintains a (1 + o (1)Δ-vertex coloring with O (polylog Δ) amortized update time. (3) We present a simple, deterministic algorithm which maintains a (2Δ – 1)-edge coloring with O (log Δ) worst-case update time. This improves the recent O (Δ)-edge coloring algorithm with worst-case update time [4].

STOC Conference 2017 Conference Paper

Subquadratic submodular function minimization

• Deeparnab Chakrabarty
• Yin Tat Lee
• Aaron Sidford
• Sam Chiu-wai Wong

SODA Conference 2015 Conference Paper

On (1, ∊ )-Restricted Assignment Makespan Minimization

• Deeparnab Chakrabarty
• Sanjeev Khanna
• Shi Li 0001

Makespan minimization on unrelated machines is a classic problem in approximation algorithms. No polynomial time (2 – δ)-approximation algorithm is known for the problem for constant δ > 0. This is true even for certain special cases, most notably the restricted assignment problem where each job has the same load on any machine but can be assigned to one from a specified subset. Recently in a breakthrough result, Svensson [16] proved that the integrality gap of a certain configuration LP relaxation is upper bounded by 1. 95 for the restricted assignment problem; however, the rounding algorithm is not known to run in polynomial time. In this paper we consider the (1, ε)-restricted assignment problem where each job is either heavy ( p j = 1) or light ( p j = ε), for some parameter ε > 0. Our main result is a (2 – δ)-approximate polynomial time algorithm for the (1, ε)-restricted assignment problem for a fixed constant δ > 0. Even for this special case, the best polynomial-time approximation factor known so far is 2. We obtain this result by rounding the configuration LP relaxation for this problem. A simple reduction from vertex cover shows that this special case remains NP-hard to approximate to within a factor better than 7/6.

FOCS Conference 2015 Conference Paper

Online Buy-at-Bulk Network Design

• Alina Ene
• Deeparnab Chakrabarty
• Ravishankar Krishnaswamy
• Debmalya Panigrahi

We present the first non-trivial online algorithms for the non-uniform, multicommodity buy-at-bulk (MC-BB) network design problem. Our competitive ratios qualitatively match the best known approximation factors for the corresponding offline problems. In particular, we show: 1. A polynomial time online algorithm with a poly-logarithmic competitive ratio for the MC-BB problem in undirected edge-weighted graphs. 2. A quasi-polynomial time online algorithm with a poly-logarithmic competitive ratio for the MC-BB problem in undirected node-weighted graphs. 3. For any fixed ε > 0, a polynomial time online algorithm with a competitive ratio of O̅(k {1/2+ε} polylog(n)) (where k is the number of demands) for MC-BB in directed graphs. 4. Algorithms with matching competitive ratios for the prize-collecting variants of all the above problems. Prior to our work, a logarithmic competitive ratio was known for undirected, edge-weighted graphs only for the special case of uniform costs (Awerbuch and Azar, FOCS 1997), and a polylogarithmic competitive ratio was known for the edge-weighted single-sink problem (Meyerson, SPAA 2004). To the best of our knowledge, no previous online algorithm was known, even for uniform costs, in the node-weighted and directed settings. Our main engine for the results above is an online reduction theorem of MC-BB problems to their single-sink (SS-BB) counterparts. We use the concept of junction-tree solutions (Chekuri et al. , FOCS 2006) that play an important role in solving the offline versions of the problem via a greedy subroutine -- an inherently offline procedure. Our main technical contribution is in designing an online algorithm using only the existence of good junction-trees to reduce an MC-BB instance to multiple SS-BB sub-instances. Along the way, we also give the first non-trivial online node-weighted/directed single-sink buy-at-bulk algorithms. In addition to the new results, our generic reduction also yields new proofs of recent results for the online node-weighted Steiner forest and online group Steiner forest problems.

SODA Conference 2015 Conference Paper

Property Testing on Product Distributions: Optimal Testers for Bounded Derivative Properties

• Deeparnab Chakrabarty
• Kashyap Dixit
• Madhav Jha
• C. Seshadhri 0001

The primary problem in property testing is to decide whether a given function satisfies a certain property, or is far from any function satisfying it. This crucially requires a notion of distance between functions. The most prevalent notion is the Hamming distance over the uniform distribution on the domain. This restriction to uniformity is rather limiting, and it is important to investigate distances induced by more general distributions. In this paper, we give simple and optimal testers for bounded derivative properties over arbitrary product distributions. Bounded derivative properties include fundamental properties such as monotonicity and Lipschitz continuity. Our results subsume almost all known results (upper and lower bounds) on monotonicity and Lipschitz testing. We prove an intimate connection between bounded derivative property testing and binary search trees (BSTs). We exhibit a tester whose query complexity is the sum of expected depths of optimal BSTs for each marginal. Furthermore, we show this sum-of-depths is also a lower bound. A technical contribution of our work is an optimal dimension reduction theorem for all bounded derivative properties, which relates the distance of a function from the property to the distance of restrictions of the function to random lines. Such a theorem has been elusive even for monotonicity, and our theorem is an exponential improvement to the previous best known result.

NeurIPS Conference 2014 Conference Paper

Provable Submodular Minimization using Wolfe's Algorithm

• Deeparnab Chakrabarty
• Prateek Jain
• Pravesh Kothari

Owing to several applications in large scale learning and vision problems, fast submodular function minimization (SFM) has become a critical problem. Theoretically, unconstrained SFM can be performed in polynomial time (Iwata and Orlin 2009), however these algorithms are not practical. In 1976, Wolfe proposed an algorithm to find the minimum Euclidean norm point in a polytope, and in 1980, Fujishige showed how Wolfe's algorithm can be used for SFM. For general submodular functions, the Fujishige-Wolfe minimum norm algorithm seems to have the best empirical performance. Despite its good practical performance, theoretically very little is known about Wolfe's minimum norm algorithm -- to our knowledge the only result is an exponential time analysis due to Wolfe himself. In this paper we give a maiden convergence analysis of Wolfe's algorithm. We prove that in t iterations, Wolfe's algorithm returns a O(1/t)-approximate solution to the min-norm point. We also prove a robust version of Fujishige's theorem which shows that an O(1/n^2)-approximate solution to the min-norm point problem implies exact submodular minimization. As a corollary, we get the first pseudo-polynomial time guarantee for the Fujishige-Wolfe minimum norm algorithm for submodular function minimization. In particular, we show that the min-norm point algorithm solves SFM in O(n^7F^2)-time, where $F$ is an upper bound on the maximum change a single element can cause in the function value.

STOC Conference 2013 Conference Paper

A o(n) monotonicity tester for boolean functions over the hypercube

• Deeparnab Chakrabarty
• C. Seshadhri 0001

Given oracle access to a Boolean function f:{0,1} n -> {0,1}, we design a randomized tester that takes as input a parameter ε>0, and outputs Yes if the function is monotonically non-increasing, and outputs No with probability >2/3, if the function is ε-far from being monotone, that is, f needs to be modified at ε-fraction of the points to make it monotone. Our non-adaptive, one-sided tester makes ~O(n 5/6 ε -5/3 ) queries to the oracle.

STOC Conference 2013 Conference Paper

Optimal bounds for monotonicity and lipschitz testing over hypercubes and hypergrids

• Deeparnab Chakrabarty
• C. Seshadhri 0001

FOCS Conference 2009 Conference Paper

On Allocating Goods to Maximize Fairness

• Deeparnab Chakrabarty
• Julia Chuzhoy
• Sanjeev Khanna

We consider the Max-Min Allocation problem: given a set A of m agents and a set I of n items, where agent A ¿ A has utility u A, i for item i ¿ I, our goal is to allocate items to agents so as to maximize fairness. Specifically, the utility of an agent is the sum of its utilities for the items it receives, and we seek to maximize the minimum utility of any agent. While this problem has received much attention recently, its approximability has not been well-understood thus far: the best known approximation algorithm achieves an O¿(¿m)-approximation, and in contrast, the best known hardness of approximation stands at 2. Our main result is an algorithm that achieves an O¿(n ¿ )-approximation for any ¿ = ¿((log log n)/(log n)) in time n O(1/¿). In particular, we obtain poly-logarithmic approximation in quasipolynomial time, and for every constant ¿ > 0, we obtain an O¿(n ¿ )-approximation in polynomial time. An interesting technical aspect of our algorithm is that we use as a building block a linear program whose integrality gap is ¿(¿m). We bypass this obstacle by iteratively using the solutions produced by the LP to construct new instances with significantly smaller integrality gaps, eventually obtaining the desired approximation. As a corollary of our main result, we also show that for any constant ¿ > 0, an O(m ¿ )-approximation can be achieved in quasi-polynomial time. We also investigate the special case of the problem, where every item has non-zero utility for at most two agents. This problem is hard to approximate up to any factor better than 2. We give a factor 2-approximation algorithm.

FOCS Conference 2008 Conference Paper

On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP

• Deeparnab Chakrabarty
• Gagan Goel

In this paper we consider the following maximum budgeted allocation (MBA) problem: Given a set of m indivisible items and n agents; each agent i willing to pay b ij on item j and with a maximum budget of B i, the goal is to allocate items to agents to maximize revenue. The problem naturally arises as auctioneer revenue maximization in budget-constrained auctions and as winner determination problem in combinatorial auctions when utilities of agents are budgeted-additive. We give a 3/4-approximation algorithm for MBA improving upon the previous best of sime0. 632[2, 10]. Our techniques are based on a natural LP relaxation of MBA and our factor is optimal in the sense that it matches the integrality gap of the LP. We prove it is NP-hard to approximate MBA to any factor better than 15/16, previously only NP-hardness was known [21, 17]. Our result also implies NP- hardness of approximating maximum submodular welfare with demand oracle to a factor better than 15/16, improving upon the best known hardness of 275/276[10]. Our hardness techniques can be modified to prove that it is NP-hard to approximate the Generalized Assignment Problem (GAP) to any factor better than 10/11. This improves upon the 422/423 hardness of [7, 9]. We use iterative rounding on a natural LP relaxation of MBA to obtain the 3/4-approximation. We also give a (3/4 - epsiv) -factor algorithm based on the primal-dual schema which runs in O(nm) time, for any constant epsiv > 0.