Submodular functions are a key concept in combinatorial optimization. Algorithms that involve submodular functions usually assume that they are given by a (value) oracle. Many interesting problems involving submodular functions can be solved using only polynomially many queries to the oracle, e.g., exact minimization or approximate maximization.

In this paper, we consider the problem of approximating a monotone submodular function f on a ground set of size n everywhere, after only poly(n) oracle queries. Our main result is a deterministic algorithm that makes poly(n) oracle queries and derives a function g such that, for every set S, g(S) approximates f(S) within a factor α(n), where α(n)=sqrt(n+1) for rank functions of matroids and α(n)=O(sqrt(n) log n) for general monotone submodular functions. Our result is based on approximately finding a maximum volume inscribed ellipsoid in a symmetrized polymatroid, and the analysis involves various properties of submodular functions and polymatroids.

Our algorithm is tight up to logarithmic factors. Indeed, we show that no algorithm can achieve a factor better than Ω(sqrt(n) / log n), even for rank functions of a matroid.

We consider the number of queries needed to solve the matroid intersection problem, a question raised by Welsh (1976). Given two matroids of rank r on n elements, it is known that O(nr^1.5) independence queries suffice. However, no non-trivial lower bounds are known for this problem.

We make the first progress on this question. We describe a family of instances of rank r=n/2 based on a pointer chasing problem, and prove that (log₂ 3) n - o(n) queries are necessary to solve these instances. This gives a constant factor improvement over the trivial lower bound of n for matroids of this rank.

Our proof uses methods from communication complexity and group representation theory. We analyze the communication matrix by viewing it as an operator in the group algebra of the symmetric group and explicitly computing its spectrum.

We present new algebraic approaches for several well-known combinatorial problems, including non-bipartite matching, matroid intersection, and some of their generalizations. Our work yields new randomized algorithms that are the most efficient known. For non-bipartite matching, we obtain a simple, purely algebraic algorithm with running time O(n^ω) where n is the number of vertices and ω is the matrix multiplication exponent. This resolves the central open problem of Mucha and Sankowski (FOCS 2004). For matroid intersection, our algorithm has running time O(nr^ω-1) for matroids with n elements and rank r that satisfy some natural conditions.

We consider the capacity of information networks in the absence of interference and noise. An outer bound on the rate region of these networks is presented, answering a question of Song, Yeung and Cai. This outer bound combines properties of entropy with a strong information inequality derived from the structure of the network. This blend of information theoretic and graph theoretic arguments generates many interesting results. For example, we exactly characterize the capacity of directed cycles, solving a question of Kramer and Savari. We also give the first known proof of a gap between the sparsity of an undirected graph and its capacity. Extending this result, we show that multicommodity flow solutions achieve the capacity in an infinite class of undirected graphs, thereby making important progress on a conjecture of Li and Li. This result is in sharp contrast to the situation with directed graphs, where we present a family of graphs in which the gap between the capacity and the rate achievable using multicommodity flows is linear in the size of the graph.

Scalable overlay networks such as Chord, CAN, Pastry, and Tapestry have recently emerged as flexible infrastructure for building large peer-to-peer systems. In practice, such systems have two disadvantages: They provide no control over where data is stored and no guarantee that routing paths remain within an administrative domain whenever possible. SkipNet is a scalable overlay network that provides controlled data placement and guaranteed routing locality by organizing data primarily by string names. SkipNet allows for both fine-grained and coarse-grained control over data placement: Content can be placed either on a pre-determined node or distributed uniformly across the nodes of a hierarchical naming subtree. An additional useful consequence of SkipNet's locality properties is that partition failures, in which an entire organization disconnects from the rest of the system, can result in two disjoint, but well-connected overlay networks.