Georgia Institute of Technology College of Sciences

The past few years have seen the advent of big data, which brings unprecedented convenience to our daily life. Meanwhile, from a computational point of view, a central question arises amid the exploding amount of data: how to tame big data in an economic and efficient way. In the context of matrix computations, the question consists in the ability to handle large dense matrices. In this talk, I will first introduce data-sparse hierarchical representations for dense matrices. Then I will present recent development of a new data-driven algorithm called SMASH to operate dense matrices efficiently in the most general setting. The new method not only outperforms existing algorithms but also works in high dimensions. Various experiments will be provided to justify the advantages of the new method.

In the $k$-cut problem, we are given an edge-weighted graph and want to find the least-weight set of edges whose deletion breaks the graph into $k$ connected components. Algorithms due to Karger-Stein and Thorup showed how to find such a minimum $k$-cut in time approximately $O(n^{2k-2})$. The best lower bounds come from conjectures about the solvability of the $k$-clique problem and a reduction from $k$-clique to $k$-cut, and show that solving $k$-cut is likely to require time $\Omega(n^k)$. Our recent results have given special-purpose algorithms that solve the problem in time $n^{1.98k + O(1)}$, and ones that have better performance for special classes of graphs (e.g., for small integer weights).

In this work, we resolve the problem for general graphs, by showing that for any fixed $k \geq 2$, the Karger-Stein algorithm outputs any fixed minimum $k$-cut with probability at least $\widehat{O}(n^{-k})$, where $\widehat{O}(\cdot)$ hides a $2^{O(\ln \ln n)^2}$ factor. This also gives an extremal bound of $\widehat{O}(n^k)$ on the number of minimum $k$-cuts in an $n$-vertex graph and an algorithm to compute a minimum $k$-cut in similar runtime. Both are tight up to $\widehat{O}(1)$ factors.

The first main ingredient in our result is a fine-grained analysis of how the graph shrinks---and how the average degree evolves---under the Karger-Stein process. The second ingredient is an extremal result bounding the number of cuts of size at most $(2-\delta) OPT/k$, using the Sunflower lemma.

In critical Bernoulli percolation on $\mathbb{Z}^d$ for $d$ large, it is known that there are a.s. no infinite open clusters. In particular, for n large, every path from the origin to the boundary of $[-n, n]^d$ must contain some closed edges. Let $T_n$ be the (random) minimal number of closed edges in such a path. How does $T_n$ grow with $n$? We present results showing that for d larger than the upper critical dimension for Bernoulli percolation ($d > 6$), $T_n$ is typically of the order $\log \log n$. This is in contrast with the $d = 2$ case, where $T_n$ grows logarithmically. Perhaps surprisingly, the model exhibits another major change in behavior depending on whether $d > 8$.

I will present some recent results, obtained with D. Bresch and Z. Wang, on large stochastic many-particle or multi-agent systems. Because such systems are conceptually simple but exhibit a wide range of emerging macroscopic behaviors, they are now employed in a large variety of applications from Physics (plasmas, galaxy formation...) to the Biosciences, Economy, Social Sciences...

The number of agents or particles is typically quite large, with 10^20-10^25 particles in many Physics settings for example and just as many equations. Analytical or numerical studies of such systems are potentially very complex  leading to the key question as to whether it is possible to reduce this complexity, notably thanks to the notion of propagation of chaos (agents remaining almost uncorrelated).

To derive this propagation of chaos, we have introduced a novel analytical method, which led to the resolution of two long-standing conjectures:
        _The quantitative derivation of the 2-dimensional incompressible Navier-Stokes system from the point vortices dynamics;
       _The derivation of the mean-field limit for attractive singular interactions such as in the Keller-Segel model for chemotaxis and some Coulomb gases.