Our capacity to produce and store large sets of data has increased exponentially over the course of the last two decades; the development of algorithms for sifting through it efficiently is somewhat lagging behind. Randomization is being recognized as a powerful tool, whether in constructing models on which algorithms can be tested, or in sampling the data reliably, or in speeding up and optimizing existing algorithms. In particular, basic results from random matrix and random graph theory are being employed at the forefront of scientific computing; often, assembling algorithms and producing theoretical guarantees for them requires a blend of probability, combinatorics, graph theory, numerical analysis, and optimization.
I will speak about two results, one in which randomization is used to achieve a communication-minimizing non-symmetric eigenvalue solver, and one establishing a spectral gap in bipartite biregular graphs, with applications in areas as varied as community detection, matrix completion, and error-correcting codes. This is joint work with Jim Demmel and Grey Ballard, respectively, Gerandy Brito and Kameron Harris.

In this talk we discuss an algorithm to overcome the curse of dimensionality, in possibly non-convex/time/state-dependent Hamilton-Jacobi partial differential equations. They may arise from optimal control and differential game problems, and are generally difficult to solve numerically in high dimensions.

A major contribution of our works is to consider an optimization problem over a single vector of the same dimension as the dimension of the HJ PDE instead. To do so, we consider Hopf-type formulas. The sub-problems are now independent and they can be implemented in an embarrassingly parallel fashion. That is ideal for perfect scaling in parallel computing.

The algorithm is proposed to overcome the curse of dimensionality when solving high dimensional HJ PDE. Our method is expected to have application in control theory, differential game problems, and elsewhere. A similar technique can be extended to the computational of a Hamilton-Jacobi partial differential equations in the Wasserstein space, and this is also expected to have applications in mean field control problems and mean field games.