Cole Franks

The discrepancy of a red-blue vertex coloring of a hypergraph is the maximum imbalance between the number of red and blue vertices in any edge. The discrepancy of a hypergraph is the least discrepancy of any red-blue coloring. A major open problem is the Beck-Fíala conjecture, which asserts that the discrepancy of every t-regular hypergraph is on the order of the square root of t. I will discuss some recent joint work with Michael Saks on an application of Fourier analysis to the discrepancy of random regular hypergraphs.

In many cases, a group action on a manifold can be associated with a map called a moment map. Surprisingly, the image of the manifold under this map is always a convex polytope, known as its moment polytope. Moment polytope membership can often be expressed as an optimization problem which is convex only in the Abelian case. Whether moment polytope membership can be decided in polynomial time is a fundamental open problem with deep consequences in algebraic complexity theory and elsewhere. For example, the map sending a d-tensor to its tuple of marginals is a moment map for the group GL(n)^d acting on tensors by scaling each factor. I'll discuss a recent joint work in which we obtain an extremely simple algorithm for tensor scaling, i.e. approximately scaling tensors to arbitrary prescribed marginals (whenever possible). Improving the run-time of our tensor scaling algorithm to polylog(\eps) would result in a polynomial time algorithm for moment polytope membership in this special case, and would have applications in polynomial identity testing, computing Brascamp-Lieb constants, and optimization problems related to tensor rank, to name a few.

A characterization theorem and algorithm to test, given positive semidefinite matrices P and Q and a completely positive map T, whether it is possible to pre- and post- compose T with matrix similarities so that T is both trace-preserving and maps P to Q. This generalizes the (r,c)-scaling problem, which asks, given a nonnegative matrix and vectors r and c, if the matrix can be pre- and post- multiplied by diagonals so that its row sums become r and the column sums become c.

How best to play 20 questions and a little on the theory of large deviations.

How to fairly distribute goods and services among people who may not be honest about how much they value said goods and services.