## Talks

### Efficient algorithms for tensor scaling, quantum marginals, and moment polytopes

FOCS (2018),

[slides]

### Efficient algorithms for tensor scaling, quantum marginals, and moment polytopes

CWI Networks and Optimization interest group seminar (2018),

[slides]

**Abstract**

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.

### On the Discrepancy of Random Matrices with Many Columns

CMO BIRS workshop: Analytic techniques in Theoretical Computer Science (2018),

[slides]

**Abstract**

Motivated by the Kómlos conjecture in combinatorial discrepancy, we study the discrepancy in arbitrary norms of random matrices with independent columns drawn from a lattice random variable. It is known that if the number of rows is fixed and the number columns tends to infinity, the discrepancy becomes at most twice the covering radius of the lattice spanned by the support. However, the easy argument for the above fact gives no concrete bounds on the failure probability. We prove that the failure probability is inverse polynomial in the number of rows and columns as well as a few well-motivated parameters of the random variable.

We apply these results to two models of interest, namely the t-sparse random matrices and matrices with random unit columns. For t-sparse matrices we show that the discrepancy is at most two with high probability as long as the number of columns is the cube of the number of rows (up to polylog factors) and that, for the same number of columns, the discrepancy of a matrix with random unit columns tends to zero with high probability.

Our approach uses Fourier analysis, and is in the spirit of Kuperberg, Lovett and Peled (G. Kuperberg, S. Lovett and R. Peled, STOC 2012). We prove that for matrices with many i.i.d. columns, with high probability the output of the matrix on a random point in the Boolean cube obeys a local central limit theorem.

### Operator Scaling with Specified Marginals

STOC (2018),

[slides]

**Abstract**

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.

### Mechanism Design

Rutgers Graduate Student Pizza Seminar (2016)

**Abstract**

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

### Area Paradoxes

Rutgers Graduate Student Pizza Seminar (2015)

**Abstract**

Besikovitch's construction of sets in the unit cube with volume 0.1 and arbitrarily small surface area (first few steps at right).

## Contact

### W. Cole Franks

Hill Center, Room 606

Department of Mathematics

Rutgers, The State University Of New Jersey

110 Frelinghuysen Rd.

Piscataway, NJ 08854-8019

email: wcf17 at math dot rutgers dot edu