We consider the parallel complexity of approximate 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 is a simple depth 2 algorithm with query complexity n^O(M) and the second method has depth O(n^1/3M^2/3) and query complexity O(poly(n,M)).

We give a slightly different tester than the usual one, and use the isometry theorem mentioned below to obtain a near optimal non-adaptive tester for Boolean functions on the d-dimensional hypergrid. This (sort of) ends a journey which began with Sesh and my STOC 2013 paper giving the first o(d)-tester for Boolean functions on d-dimensional hypercubes. Lesson learnt: the hypergrid is a more intersting beast than the hypercube.

In this paper we generalize Khot-Minzer-Safra's directed Talagrand isoperimetry theorem for hypergrids. This leads to a tester with optimal dependence on the dimension, but has a suboptimal dependence on the granularity. We fix this issue in the FOCS paper (mentioned above), but we lose a d^o(1) factor on the way. Not sure if that can be removed (perhaps, but it may need another idea).

Suppose you have an unknown undirected graph with positive weights on its edges, and the only access is via cut queries: you can query a subset S of vertices and obtain the total weight of edges crossing it. How many queries would you need to detect if the graph is connected? This is a very special case of submodular function minimization. It's not too hard to obtain a O(nlog n) query deterministic algorithm (it's a nice undergraduate algorithms exercise), but can one do better or is there a lower bound? In this paper, we describe a randomized algorithm which succeeds with probability 1 and makes O(n) queries in expectation. In the ALT version, we had a weaker result of a Monte-Carlo algorithm making O(nloglog n) queries with constant error probability. Another new result in this version is a deterministic O(n log n/loglog n) query algorithm showing that one can improve upon the simple case mentioned above. Can one obtain a linear query deterministic algorithm, or is there a lower bound? As of now, it's open!

We show that any polynomial query algorithm for submodular function minimization (SFM) and matroid intersection (with rank oracle), must proceed in roughly cuberoot(N) rounds of queries where N is the size of the universe. Thus, although SFM and matroid intersection can be solved efficiently, they are not highly parallelizable.

In an older paper with Prachi Goyal and Ravishankar Krishnaswamy [ICALP 2016, TALG 2020], we had introduced the non-uniform k-center problem which generalizes the k-center with outliers problem. We are given k possibly different radii balls, and we have to figure out how to place them on a metric space such that the unions of dilated versions of these cover the whole metric space. We want to make the dilation as small as possible. We proved that if the number of types is part of input, no constant factor approximation is possible. However, I have felt (and still feel) for constantly many types, there should be a O(1) approximation. And indeed, that paper we could give for 2-types of radii. We make "epsilon progress" in this paper. We show that the 2-types of radii *with outliers* has a 10-approximation. The problem of constantly many types is still open.

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(nlog 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/logn) rounds to minimize a submodular function. This improves upon the result two bullet points below, and settles the parallel complexity of query-efficient SFM up to logarithmic factors.

We consider classic clustering problems in continuous spaces where centers can be picked from a potentially infinite set. Triangle inequality lets us reduce to the "discrete" case where the centers are picked from among the points to be clustered itself, at a loss of beta in the approximation factor, where beta depends on the objective function. For instance, for k-median, beta is 2 while for k-means, beta is 4. This paper asks: can one design algorithms without incurring this beta overhead. We show a technique based on round-and-cut which allows us to bypass this beta factor loss for certain problems.

Motivated by individually fair clustering, we look at the question of "opening" k-centers in a metric space (a) minimize the k-median objective of sum of every client to the nearest open center, (b) with the constraint that every client j has an open center within distance some specified amount r(j). It is not hard to see that just checking if there is any solution satisfying (b) is as hard as the k-center problem. One thus looks for bi-criteria algorithms. We show that a modification of the old Charikar-Guha-Shmoys-Tardos rounding can give an (8,8)-approximation : we violate the "fairness" constraint by factor 8, and our cost is within 8 times OPT.

Given an unknown non-negative N-dimensional vector x, suppose you could "measure" it using a linear measurement, that is, obtain a*x for any N-dimensional query vector a. How many queries do you need to deterministically return one element from x's support? The answer is log N, using binary search. However, binary search is an adaptive algorithm which takes log N rounds of queries. What is the answer if you had only 2 rounds allowed? A moment's thought will show you how to do this in sqrt(N) queries per round. In this paper we prove this is tight. We also look at the related and more general question of finding a spanning tree in a graph using "cut-queries" or "independent set" queries, and obtain rounds-versus-query trade-offs.

In the usual k-center problem, one wants to open k-centers so that the maximum distance of a point to an open center is minimized. However, not all points may be equal, and one could ask the "priority" version where the distance of a point is multiplied by their priority, and the maximum of this prioritized distance is to be minimized. Indeed, this also has a 2-approximation algorithm which is tight even for the vanilla k-center problem, and was known since 1987. In this paper we look at the problem in the presence of outliers, that is, when the maximum can be taken over a fraction of the clients. The vanilla k-center with outliers has a 2-approximation. We give a 9-approximation for the priority k-center with outliers. Our framework also is able to handle more general constraints (knapsack and matroid) on the opened centers (though we take a hit in the approximation factor in the knapsack case). We show that better than 3-approximation is not possible, but bridging the gap between 3 and 9 may need another idea.

Given a non-negative matrix, can we multiply the rows and columns by scalars so that the scaled matrix has prescribed row and columns sums? The Sinkhorn-Knopp algorithm is a simple iterative procedure which first scales all the rows and then scales all the columns, and repeats this getting closer to the desired matrix. Although simple and known for around 80 years, the analysis of the procedure is still incomplete. In this paper, we give a better and simpler error analysis of this algorithm. A key tool is a new inequality connecting KL-divergence between two distributions and their ell_2 norms.

In SODA 2018, we gave a o(d)polylog n tester for Boolean monotonicity testing over the d-dimensional hypergrid [n]^d. In this work, we show how to remove the dependence on n. Using this, we get the first o(d) tester for Boolean functions over R^d. The main idea is domain reduction. Sample k = poly(d) coordinates iid from each of the d-dimensions and look at the function restricted to this sub-hypergrid. We show that if the original function is eps-far, then whp the restricted function is O(eps) far. Then we apply the SODA 2018 result.

In MOBIHOC 2016, we studied a decentralized randomized algorithm for graph coloring with D+1 colors, where D is the maximum degree, in a model where nodes can't talk to each other and the only information they know at any time is whether or not some neighbor has the same color as itself. In this paper, we show how a modification of the same algorithm (under the same model) can return a valid coloring in O(nlog D) expected time. This is a generalization of the coupon collector problem (when D =n-1) and indeed uses the same.

We look at a generalization of the k-center problem and the k-center with outliers problem. We are given k possibly different radii balls, and we have to figure out how to place them on a metric space such that the unions of dilated versions of these cover the whole metric space. We want to make the dilation as small as possible.

A real-valued function defined over the d-dimensional hypercube is unate if across every coordinate it is consistently either non-increasing or non-decreasing. We investigate the question of testing unateness. We provide optimal testers and prove that adaptivity helps (although by a modest logarithmic factor). This differentiates it from monotonicity testing where adaptivity doesn't help in general.

We give fully dynamic deterministic algorithms for the minimum vertex cover and the maximum fractional matching problem which have O(1)-amortized update time and O(1)-approximation. Previously, Solomon gave a randomized O(1)-amortized update time algorithms for maintaining a maximal matching. Our results also generalize to the hypergraph setting. Similar results were obtained concurrently by Gupta et al.

We give a black-box algorithm which converts any vanilla clustering algorithm to a fair one (based on the disparate impact notion) whose approximation factor is only "slightly" worse, with an "additive hit" in the fairness. This works for k-center, k-median, and k-means objectives.

We give the fastest known algorithms for matroid intersection when the matroids are given as independence or rank oracles.

Given n jobs and m machines with unrelated processing times, and a monotone, symmetric norm on m-dimensions, find an assignment of jobs to machines which minimizes f on the load-vector. This was considered in our STOC 2019 paper. We give a direct and simpler 4-approximation.

Generalizes our ICALP 2018 paper below to work for any monotone, symmetric norm. Gives a general framework and also considers the load balancing problem.

We show a simple O(I*polylog(n)) adaptive Boolean monotonicity tester for functions of total influence I. One upshot is that if adaptive Boolean testing is hard, the functions need to have high influence.

Consider a generalization of the k-center/supplier problem where the constraint on where the facilities can be opened is not a cardinality constraint, but rather the set of open facilities is restricted to be in some collection of down-closed sets. What is the complexity of the problem? What happens when we have outliers? In this paper, we completely characterize the complexity of both these problems. As a by-product, we get an optimal 3-approximation to the weighted k-center problem with outliers. Before this, no true approximation was known.

Consider a facility location version where you need to open k facilities, and clients connect to the nearest open facility, but the objective is the sum of the \ell-largest connection costs. This interpolates the problem between the k-center and the k-median problem. We give a O(1)-approximation to this, and its generalization, the ordered median problem.

There are simple and classic linear time algorithsm for (Δ+1)- vertex coloring and (2Δ−1)-edge coloring in a graph with maximum degree Δ. What happens when the graphs is dymamic : edges are being inserted and deleted? Can we maintain a legal coloring with small update times? We show the following three results.
(1) A randomized algorithm which maintains a (Δ+1)-vertex coloring with O(logΔ) expected amortized update time.
(2) A deterministic algorithm which maintains a (1+o(1))Δ-vertex coloring with O(polylogΔ) amortized update time.
(3) A deterministic algorithm which maintains a (2Δ−1)-edge coloring with O(logΔ) worst-case update time.
The last seems to be a textbook algoithm and improves upon the recent O(Δ)-edge coloring algorithm with O(√Δ) worst-case update time by Barenboim and Maimon.

Testing monotonicity of Boolean functions over the d-dimensional hypercube generated a lot of attention recently leading to testers whose running time grows as square-root of d. What about Boolean functions defined over the d-dimensional hypergrid? The techniques that lead to sqrt(d) testers seem hard to generalize. In this paper we give the first sublinear in d tester -- the caveat is that we have a polylogarithmic dependence on n, the granularity in each dimension. A key contribution is isoperimetry results for a strucuture we call the augmented hypergrid.

In the buy-at-bulk network design problem, we are given a graph with source-sink pairs with demand, concave costs on edges, and the goal is to route these demands concurrently so as to minimize the total cost. The concavity of edges captures the economies of scale. We consider the online version where the demands appear one-by-one and need to be routed on the fly. We give the first polylogarithmic competitive ratio for this problem.

Submodular functions on an n-element universe can be minimized in polynomial time. The best known algorithms make O(n³) queries or O(n² polylog M) queries, where M is the largest absolute value of the function. In this paper, we give a O(nM³)-time exact, and a O(n^5/3/eps²))-time eps-approximate algorithm. The latter is for functions in [-1,1] and the approximation is additive.

In the k-center problem, we need to install k-centers in a metric space and assign clients to them so as to minimize the max client-center distance. In the usual homogeneous capacitated version, each of the k-centers have the same capacity constraint indicating the maximum number of clients it can serve. We consider the case when the k-centers have different capacity constraints. Our problem is different from the non-uniform capacitated k-center problem where instead each point on the metric space has a capacity constraint indicating the maximum number of clients that can be served by a center opened at that point. We give one application to a network scheduling problem.

In property testing, the concept of distance is crucial and is often defined using the Hamming distance between objects. For instance, a function's distance to monotonicity is often defined to be the fraction of domain points at which it needs to be modified to make it monotone. How does the situation change when the underlying distribution used to measure the distance is not uniform. In this paper, we look at arbitrarty product distributions, and essentially show the quality of a monotonicity tester is worst for the uniform distribution. More precisely, we prove that the query complexity is essentially the entropy (but not quite) of the product distribution by exhibiting simple testers and not-so-simple lower bounds. Our results hold for a general class of properties which we call bouned derivative properties.

The theoretical heart of the paper is a (new?) decentralized algorithm for graph coloring with D+1 colors, where D is the maximum degree. In the application, nodes can't talk to each other and the only information they know at any time is whether or not some neighbor has the same color as itself. The algorithm is a randomized coloring algorithm which returns a valid coloring in O(nD) expected time.

We study a generalization of facility location and minimum latency problems which generalizes a host of comb opt problems. We give (almost) optimal algorithms with logarithmic approximations, and constant approximations for special cases. On the way, we develop an LP based approach to minimum latency which we believe (but can't prove) should give better approximation algorithms for the same.

We make progress on Boolean monotonicity testing giving the first sublinear (in dimension) algorithms. On the way we prove a new directed isoperimetry result, and use it to analyze random walks on the directed hypercube. Note: The proceedings version has a bug and the claimed n^{5/6} is incorrect and we can only achieve n^{7/8}. This has been corrected in the full version linked to above. Also check out the FOCS 2014 paper by Chan, Servedio, and Tan.

In a breakthrough in 2011, Svensson showed that the value of the optimum makespan can be estimated up to a factor of 1.95, in the restricted assignment setting. However, a polynomial time algorithm to obtain a schedule achieving the corresponding makespan is as of yet not known. In this paper, we look at a special case of restricted assignment problem where jobs are of two sizes - 1 or eps. We demonstrate a polynomial time (2 - delta) approximation for some constant delta > 0 which doesn't depend on epsilon.

Motivated by a question in this paper, we study whether coverage functions can be recognized and tested. We give a polytime reconstruction algorithm for succinct coverage functions. At the same time, we show that without succinctness, even certificates of "non-coverageness" could be exponentially large.

Capacitated Network Design is the natural generalization of the SNDP problem, where we need to pick the cheapest subgraph of a capacitated graphs satisfying certain cut constraints. Unlike the unit capacity version, this problem seems harder. For instance, the directed version is label cover hard even when there's a single pair cut constraint. We give logarithmic approximations when there are global cut constaints, and when picking multiple copies of edges are allowed.

In 1976, Wolfe proposed an algorithm to find the minimum Euclideam norm point in a polytope. He proved finite convergence of his algorithm, although the known running time is exponential in the number of vertices of the polytope. In 1980, Fujishige observed that Wolfe's minimum norm point algorithm can be used to minimize submodular functions by running it on the function's base polytope. In practice, it has been observed that this Fujishige-Wolfe minimum norm point algorithm works decently well, although, no theoretical guarantee (apart from Wolfe's) was known. In this paper, we make some progress. We prove that Wolfe's algorithm has 1/t convergence, in that, in O(t) iterations it returns a t-approximate solution. Along with a robust version of Fujishige's theorem regarding submodular functions, this implies a pseudopolynomial time for submodular minimization.

In an allocation setting where preferences of agents are orders over outcomes rather than cardinal numbers for each preference, the notion of social welfare is not well defined or agreed upon. Furthermore, when mechanisms are randomized, the concept of truthfulness comes into question. In this paper, wearing our TCS hats, we propose a notion of welfare called rank approximation. A mechanism has c-rank approximation if for all i between 1 and n, the number of agents getting their top i choices is within c-factor of the allocation tailored to maximize the number of agents getting their top i choices. We also propose a notion of truthfulness, called lex-truthfulness, in randomized ordinal mechanisms. This notion is nicely sandwiched between two notions studied in the literature. Equipped with these notions, we define matching market mechanisms which are lex-truthful and have optimal rank approximation.

We complement our STOC 2013 paper with a matching lower bound of Omega(d log n/eps). This holds for adaptive, two-sided testers. On the flip side, this is only for functions which have unbounded range.

The best known approximation, due to this paper, is based on what we call hypergraphic LP relaxations. This paper was independent and concurrent of their work where we study a list of hypergraphic relaxations and prove their equivalence. We also prove a "better-than-2" integrality gap, but this has been since then improved.

In this paper, we show that the capacitated network design problem is Label-Cover hard. Here, we are given a capacitated graph G and two vertices s and t. The goal is to find the smallest subgraph H of G so that s can route R units of flow to t. We also show a flow-additivity theorem for undirected graphs which, somewhat surprisingly, shows that the max flow between a set of vertices to a sink t is at least half the sum of the individual flows of these vertices (provided the set is minimal)

In Internet ad auctions, the search engine often has to "throttle" budget constrained advertisers to spread their expenditure equally across a specified time period. We ask how should this `budget-smoothing' be done? We put on our game theoretic hats and propose a notion of regret-free smoothing policies. We show these always exist, and for single slot auctions can be found in polynomial time via an algorithm which smells of Gale-Shapley's deferred acceptance algorithm. Finally, we design a heuristic for budget smoothing which performs considerably better than existing benchmark heuristics.

We give optimal testers for monotonicity over the hypercube and hypergrid domain. This settles a long standing question in property testing. Our methods are quite general, and applies to first derivative properties, which includes the Lipschitz property as well. The main technique is via matchings and alternate paths on the hypercube and hypergrids.

We try to explore the notion of welfare in matching markets where the users have ordinal preferences rather than cardinal values. Our contribution is a definition, and to analyze two existing mechanisms (RSD + PS), and prove their optimality.

In this paper we describe a new "geometric" relaxation for the Steiner tree problem which turns out to be equivalent to the bidirected cut relaxation. It also shows an upper bound of 4/3 on the integrality gap for quasi-bipartite graphs, which at the time was the best known. The current best upper bound is 73/60 given in this paper.

Byrka et al. proved a 1.55 upper bound on the hypergraphic relaxation for Steiner trees. However, their proof was based on Robbins-Zelikovsky algorithm. In this paper, we give a shorter proof based on iterative randomized rounding.

The paper explores the following question: suppose an Integer program ( min c*x Ax >= b, x in {0,1}) has integrality gap a, where A is a 0,1 matrix, can one say anything about the "capacitated" version of the IP where each column of A is multiplied by an arbitrary positive integer? That is, is there a relation between a covering problem (say covering a line using intervals) with a version where each element has a demand and each set has a supply. We answer a "conditional" yes: we define a related 0,1-optimization problem called the priority version, and if the priority version has integrality gap b, the capacitated version has an O(a+b) algorithm. It would've been nice if b was O(a), and indeed we show in some problems that is the case, but this paper dashed that hope for general covering IPs.