I am a sixth year PhD student under
Michael Saks. I am interested in discrete math and theoretical computer science.
Along with Aditya Potokuchi and Michael Saks, I coorganize the Theory of Computing Reading Seminar. To see more past papers, take a look at the old TOC reading seminar website.
(TA, Fall 2016)
with Michael Saks (2018)
with Peter Bürgisser, Ankit Garg, Rafael Oliveira, Michael Walter, and Avi Wigderson (2018)
[To appear, FOCS 2018][arXiv]
with Philip Chodrow, Brian Lins (2013)
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.
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.
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 to determine whether three given positive-semidefinite matrices can arise as marginals of a pure state.
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.
How to save a 4/729 fraction of axis-parallel squares using infinite, straight-line cuts. Following the paper by Weise et. al.
Besikovitch's construction of sets in the unit cube with volume 0.1 and arbitrarily small surface area (first few steps at right).
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
wcf17 at math dot rutgers dot edu