Search for: All records

This paper introduces the idemetric property, which formalizes the idea that, in many social and information networks, most nodes have similar distances between them. The paper shows that samples from standard generative models (preferential attachment, etc.) are idemetric in our sense. The paper also considers algorithmic applications. For example, we prove that a single breadth-first search provides a solution to the all-pairs shortest paths problem, so long as one is prepared to accept paths which are of stretch close to 2 with high probability. 

This paper initiates the study of the communication complexity of fair division with indivisible goods. It focuses on some of the most well-studied fairness notions (envy-freeness, proportionality, and approximations thereof) and valuation classes (submodular, subadditive and unrestricted). Within these parameters, the results completely resolve whether the communication complexity of computing a fair allocation (or determining that none exist) is polynomial or exponential (in the number of goods), for every combination of fairness notion, valuation class, and number of players, for both deterministic and randomized protocols. 

This paper considers the problems of maximizing a continuous non-monotone submodular function over the hypercube, both with and without coordinate-wise concavity. This family of optimization problems has several applications in machine learning, economics, and communication systems. The main result is the first 1/2-approximation algorithm for continuous submodular function maximization; this approximation factor of 1/2 is the best possible for algorithms that only query the objective function at polynomially many points. For the special case of DR-submodular maximization, i.e. when the submodular functions are also coordinate-wise concave along all coordinates, we provide a different 1 2-approximation algorithm that runs in quasi-linear time. 

This paper studies the power and limitations of posted prices in multi-unit markets, where agents arrive sequentially in an arbitrary order. The paper shows upper and lower bounds on the largest fraction of the optimal social welfare that can be guaranteed with posted prices, under a range of assumptions about the designer’s information and agents’ valuations. Our results provide insights about the relative power of uniform and non-uniform prices, the relative difficulty of different valuation classes, and the implications of different informational assumptions. Among other results, we prove constant-factor guarantees for agents with (symmetric) subadditive valuations, even in an incomplete-information setting and with uniform prices. 

We introduce an abstract and strong model of massively parallel computation, where essentially the only restrictions are that the “fan-in” of each machine is limited to s bits, where s is smaller than the input size n, and that computation proceeds in synchronized rounds, with no communication between different machines within a round. Lower bounds on round complexity in this model apply to every computing platform that shares the most basic design principles of MapReduce-type systems. We apply a variant of the “polynomial method” to capture restrictions obeyed by all such massively parallel computations. This connection allows us to translate a lower bound on the (approximate) polynomial degree of a Boolean function to a lower bound on the round complexity of every (randomized) massively parallel computation of that function. These lower bounds apply even in the “unbounded width” version of our model, where the number of machines can be arbitrarily large. As one example of our general results, computing any non-trivial monotone graph property — such as any of the standard connectivity problems — requires a super-constant number of rounds when every machine can accept only a sub-polynomial (in n) number of input bits s. This lower bound constitutes significant progress on a major open question in the area, 

This paper considers a basic problem at the interface of submodular optimization and online learning. In the online unconstrained submodular maximization problem, there is a universe [n] = {1, 2, . . . , n} and a sequence of T nonnegative (not necessarily monotone) submodular functions arrive over time. The goal is to design a computationally efficient online algorithm, which chooses a subset of [n] at each time step as a function only of the past, such that the accumulated value of the chosen subsets is as close as possible to the maximum total value of a fixed subset in hindsight. Our main result is a polynomial time no-1/2-regret algorithm for this problem, meaning that for every sequence of nonnegative submodular functions, the algorithm’s expected total value is at least 1/2 times that of the best subset in hindsight, up to an error term sublinear in T. The factor of 1/2 cannot be improved upon by any polynomial-time online algorithm when the submodular functions are presented as value oracles. 

This paper proposes a new distribution-free model of social networks. The definitions are motivated by one of the most universal signatures of social networks, triadic closure—the property that pairs of vertices with common neighbors tend to be adjacent. Our most basic definition is that of a c-closed graph, where for every pair of vertices u, v with at least c common neighbors, u and v are adjacent. We study the classic problem of enumerating all maximal cliques, an important task in social network analysis. We prove that this problem is fixed-parameter tractable with respect to c on c-closed graphs. Our results carry over to weakly c-closed graphs, which only require a vertex deletion ordering that avoids pairs of non-adjacent vertices with c common neighbors. Numerical experiments show that well-studied social networks with thousands of vertices tend to be weakly c-closed for modest values of c.