Georgia Institute of Technology College of Sciences

This concerns general gradient-like dynamical systems in Banach space with the property that there is a manifold along which solutions move slowly compared to attraction in the transverse direction. Conditions are given on the energy (or, more generally, Lyapunov functional) that ensure solutions starting near the manifold stay near for a long time or even forever. Applications are given with the vector Allen-Cahn and Cahn-Morral equations. This is joint work with Giorgio Fusco and Georgia Karali.

For integers k>2 and \ell0, there exist \epsilon>0 and C>0 such that for sufficiently large n that is divisible by k-\ell, the union of a k-uniform hypergraph with minimum vertex degree \alpha n^{k-1} and a binomial random k-uniform hypergraph G^{k}(n,p) on the same n-vertex set with p\ge n^{-(k-\ell)-\epsilon} for \ell\ge 2 and p\ge C n^{-(k-1)} for \ell=1 contains a Hamiltonian \ell-cycle with high probability. Our result is best possible up to the values of \epsilon and C and completely answers a question of Krivelevich, Kwan and Sudakov. This is a joint work with Jie Han.

As a generalization of many classic problems in combinatorial optimization, submodular optimization has found a wide range of applications in machine learning (e.g., in feature engineering and active learning). For many large-scale optimization problems, we are often concerned with the adaptivity complexity of an algorithm, which quantifies the number of sequential rounds where polynomially-many independent function evaluations can be executed in parallel. While low adaptivity is ideal, it is not sufficient for a (distributed) algorithm to be efficient, since in many practical applications of submodular optimization the number of function evaluations becomes prohibitively expensive. Motivated by such applications, we study the adaptivity and query complexity of adaptive submodular optimization. Our main result is a distributed algorithm for maximizing a monotone submodular function with cardinality constraint $k$ that achieves a $(1-1/e-\varepsilon)$-approximation in expectation. Furthermore, this algorithm runs in $O(\log(n))$ adaptive rounds and makes $O(n)$ calls to the function evaluation oracle in expectation. All three of these guarantees are optimal, and the query complexity is substantially less than in previous works. Finally, to show the generality of our simple algorithm and techniques, we extend our results to the submodular cover problem. Joint work with Vahab Mirrokni and Morteza Zadimoghaddam (arXiv:1807.07889).

We will give a brief introduction to matroids with a focus on representable matroids. We will also discuss the Plücker embedding of the Grassmannian.