Author name cluster

Deeparnab Chakrabarty

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

22 papers

2 author rows

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

The problem of testing monotonicity for Boolean functions on the hypergrid, f :[ n ] d → {0,1} is a classic topic in property testing. When n =2, the domain is the hypercube. For the hypercube case, a breakthrough result of Khot-Minzer-Safra (FOCS 2015) gave a non-adaptive, one-sided tester making O (ε −2 √ d ) queries. Up to polylog d and ε factors, this bound matches the Ω(√ d )-query non-adaptive lower bound (Chen-De-Servedio-Tan (STOC 2015), Chen-Waingarten-Xie (STOC 2017)). For any n > 2, the optimal non-adaptive complexity was unknown. A previous result of the authors achieves a O ( d 5/6 )-query upper bound (SODA 2020), quite far from the √ d bound for the hypercube. In this paper, we resolve the non-adaptive complexity of monotonicity testing for all constant n , up to poly (ε −1 log d ) factors. Specifically, we give a non-adaptive, one-sided monotonicity tester making O (ε −2 n √ d ) queries. From a technical standpoint, we prove new directed isoperimetric theorems over the hypergrid [ n ] d . These results generalize the celebrated directed Talagrand inequalities that were only known for the hypercube.

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

We describe a Õ ( d 5/6 )-query monotonicity tester for Boolean functions f: [ n ] d → {0, 1} on the n hypergrid. This is the first o ( d ) monotonicity tester with query complexity independent of n. Motivated by this independence of n, we initiate the study of monotonicity testing of measurable Boolean functions f: ℝ d → {0, 1} over the continuous domain, where the distance is measured with respect to a product distribution over ℝ d. We give a Õ ( d 5/6 )-query monotonicity tester for such functions. Our main technical result is a domain reduction theorem for monotonicity. For any function f: [ n ] d → {0, 1}, let ε f be its distance to monotonicity. Consider the restriction of the function on a random [ k ] d sub-hypergrid of the original domain. We show that for k = poly( d / ε f ), the expected distance of the restriction is. Previously, such a result was only known for d = 1 (Berman-Raskhodnikova-Yaroslavtsev, STOC 2014). Our result for testing Boolean functions over [ n ] d then follows by applying the d 5/6 · poly(1/ ε log n, log d )-query hypergrid tester of Black-Chakrabarty-Seshadhri (SODA 2018). To obtain the result for testing Boolean functions over ℝ d, we use standard measure theoretic tools to reduce monotonicity testing of a measurable function f to monotonicity testing of a discretized version of f over a hypergrid domain [ N ] d for large, but finite, N (that may depend on f ). The independence of N in the hypergrid tester is crucial to getting the final tester over ℝ d.

STOC Conference 2019 Conference Paper

Approximation algorithms for minimum norm and ordered optimization problems

Deeparnab Chakrabarty
Chaitanya Swamy

In many optimization problems, a feasible solution induces a multi-dimensional cost vector. For example, in load-balancing a schedule induces a load vector across the machines. In k -clustering, opening k facilities induces an assignment cost vector across the clients. Typically, one seeks a solution which either minimizes the sum- or the max- of this vector, and these problems (makespan minimization, k -median, and k -center) are classic NP-hard problems which have been extensively studied. In this paper we consider the minimum-norm optimization problem. Given an arbitrary monotone, symmetric norm, the problem asks to find a solution which minimizes the norm of the induced cost-vector. Such norms are versatile and include ℓ p norms, Top-ℓ norm (sum of the ℓ largest coordinates in absolute value), and ordered norms (non-negative linear combination of Top-ℓ norms), and consequently, the minimum-norm problem models a wide variety of problems under one umbrella, We give a general framework to tackle the minimum-norm problem, and illustrate its efficacy in the unrelated machine load balancing and k -clustering setting. Our concrete results are the following. (a) We give constant factor approximation algorithms for the minimum norm load balancing problem in unrelated machines, and the minimum norm k -clustering problem. To our knowledge, our results constitute the first constant-factor approximations for such a general suite of objectives. (b) For load balancing on unrelated machines, we give a (2+ε)-approximation for ordered load balancing (i.e., min-norm load-balancing under an ordered norm). (c) For k -clustering, we give a (5+ε)-approximation for the ordered k -median problem, which significantly improves upon the previous-best constant-factor approximation (Chakrabarty and Swamy (ICALP 2018); Byrka, Sornat, and Spoerhase (STOC 2018)). (d) Our techniques also imply O (1) approximations to the instance-wise best simultaneous approximation factor for unrelated-machine load-balancing and k -clustering. To our knowledge, these are the first positive simultaneous approximation results in these settings. At a technical level, one of our chief insights is that minimum-norm optimization can be reduced to a special case that we call min-max ordered optimization . Both the reduction, and the task of devising algorithms for the latter problem, require a sparsification idea that we develop, which is of interest for ordered optimization problems. The main ingredient in solving min-max ordered optimization is a deterministic, oblivious rounding procedure (that we devise) for suitable LP relaxations of the load-balancing and k -clustering problem; this may be of independent interest.

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

Submodular function minimization (SFM) is a fundamental discrete optimization problem which generalizes many well known problems, has applications in various fields, and can be solved in polynomial time. Owing to applications in computer vision and machine learning, fast SFM algorithms are highly desirable. The current fastest algorithms [Lee, Sidford, Wong, 2015] run in O ( n 2 log nM · EO + n 3 log O (1) nM ) time and O ( n 3 log 2 n · EO + n 4 log O (1) n )time respectively, where M is the largest absolute value of the function (assuming the range is integers) and is the time taken to evaluate the function on any set. Although the best known lower bound on the query complexity is only Ω( n ) [Harvey, 2008], the current shortest non-deterministic proof [Cunningham, 1985] certifying the optimum value of a function requires Ω(n 2 ) function evaluations.

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

The problem of monotonicity testing over the hypergrid and its special case, the hypercube, is a classic question in property testing. We are given query access to f:[k] n -> R (for some ordered range R). The hypergrid/cube has a natural partial order given by coordinate-wise ordering, denoted by prec. A function is monotone if for all pairs x prec y, f(x) ≤ f(y). The distance to monotonicity, ε f , is the minimum fraction of values of f that need to be changed to make f monotone. For k=2 (the boolean hypercube), the usual tester is the edge tester , which checks monotonicity on adjacent pairs of domain points. It is known that the edge tester using O(ε -1 n log|R|) samples can distinguish a monotone function from one where ε f > ε. On the other hand, the best lower bound for monotonicity testing over general R is Ω(n). We resolve this long standing open problem and prove that O(n/ε) samples suffice for the edge tester. For hypergrids, known testers require O(ε -1 n log k log |R|) samples, while the best known (non-adaptive) lower bound is Ω(ε -1 n log k). We give a (non-adaptive) monotonicity tester for hypergrids running in O(ε {-1} n log k) time.

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.