## Seminars and Colloquia by Series

### Data-Driven Structured Matrix Approximation by Separation and Hierarchy

Series
Applied and Computational Mathematics Seminar
Time
Monday, February 24, 2020 - 13:55 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Dr. Difeng CaiEmory University, Department of Mathematics

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.

### The Elastica Model for Image Restoration: An Operator-Splitting Approach

Series
Applied and Computational Mathematics Seminar
Time
Friday, February 21, 2020 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Roland GlowinskiUniversity of Houston, Hong Kong Baptist University

The most popular model for Image Denoising is without any doubt the ROF (for Rudin-OsherFatemi) model. However, since the ROF approach has some drawbacks (the stair-case effect being one of them) practitioners have been looking for alternatives. One of them is the Elastica model, relying on the minimization in an appropriate functional space of the energy functional $J$ defined by

$$J(v)=\varepsilon \int_{\Omega} \left[ a+b\left| \nabla\cdot \frac{\nabla v}{|\nabla v|}\right|^2 \right]|\nabla v| d\mathbf{x} + \frac{1}{2}\int_{\Omega} |f-v|^2d\mathbf{x}$$

where in $J(v)$: (i) $\Omega$ is typically a rectangular region of $R^2$ and $d\mathbf{x}=dx_1dx_2$. (ii) $\varepsilon, a$ and $b$ are positive parameters. (iii) function $f$ represents the image one intends to denoise.

Minimizing functional $J$ is a non-smooth, non-convex bi-harmonic problem from Calculus of  Variations. Its numerical solution is a relatively complicated issue. However, one can achieve this task rather easily by combining operator-splitting and finite element approximations. The main goal of this lecture is to describe such a methodology and to present the results of numerical experiments which validate it.

### The Karger-Stein Algorithm is Optimal for k-cut

Series
ACO Student Seminar
Time
Friday, February 21, 2020 - 13:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Jason LiCS, Carnegie Mellon University

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.

### Open Forum: Pierre-Emmanuel Jabin

Series
Other Talks
Time
Friday, February 21, 2020 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Pierre-Emmanuel JabinUniversity of Maryland, College Park

This is the open forum for Pierre-Emmanuel   Jabin (https://home.cscamm.umd.edu/~jabin/)

as a candidate for Elaine M. Hubbard Chair in Mathematics.

### Critical first-passage percolation in high dimensions

Series
Stochastics Seminar
Time
Thursday, February 20, 2020 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Jack HansonCity College of New York

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$.

### Maximum Weight Internal Spanning Tree Problem

Series
Graph Theory Working Seminar
Time
Thursday, February 20, 2020 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 202
Speaker
Arti Pandey Indian Institute of Technology Ropar

Given a vertex-weighted graph G= (V, E), the MaximumWeight Internal Spanning Tree (MWIST) problem is to find a spanning tree T of G such that the total weight of internal vertices in T is maximized. The unweighted version of this problem, known as Maxi-mum Internal Spanning Tree (MIST) problem, is a generalization of the Hamiltonian path problem, and hence, it is NP-hard. In the literature lot of research has been done on designing approximation algorithms to achieve an approximation ratio close to 1. The best known approximation algorithm achieves an approximation ratio of 17/13 for the MIST problem for general graphs. For the MWIST problem, the current best approximation algorithm achieves an approximation ratio of 2 for general graphs. Researchers have also tried to design exact/approximation algorithms for some special classes of graphs. The MIST problem parameterized by the number of internal vertices k, and its special cases and variants, have also been extensively studied in the literature. The best known kernel for the general problem has size 2k, which leads to the fastest known exact algorithm with running time O(4^kn^{O(1)}). In this talk, we will talk about some selected recent results on the MWIST problem.

### Large stochastic systems of interacting particles

Series
Job Candidate Talk
Time
Thursday, February 20, 2020 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Pierre-Emmanuel JabinUniversity of Maryland, College Park

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.

### Small Ball Probability for the Smallest Singular Value of a Complex Random Matrix

Series
High Dimensional Seminar
Time
Wednesday, February 19, 2020 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Michail SarantisGeorgiaTech

Let $N_n$ be an $n\times n$ matrix whose entries are i.i.d. copies of a random variable $\zeta=\xi+i\xi'$, where $\xi,\xi'$ are i.i.d., mean zero, variance one, subgaussian random variables. We will present a result of Luh, according to which the probability that $N_n$ has a real eigenvalue is exponentially small in $n$. An interesting part of the proof is a small ball probability estimate for the smallest singular value of a complex perturbation $M_n=M+N_n$ of the original matrix.

### Lifting Covers to Braided Embeddings

Series
Geometry Topology Student Seminar
Time
Wednesday, February 19, 2020 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Sudipta KolayGeorgia Tech

An embedding of a manifold into a trivial disc bundle over another manifold is called braided if projection onto the first factor gives a branched cover. This notion generalizes closed braids in the solid torus, and gives an explicit way to construct many embeddings in higher dimensions. In this talk, we will discuss when a covering map of surfaces lift to a braided embedding.

### Descriptive combinatorics and the probabilistic method

Series
Job Candidate Talk
Time
Tuesday, February 18, 2020 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Anton BernshteynCarnegie Mellon University (CMU)

Descriptive combinatorics studies the interaction between classical combinatorial concepts, such as graph colorings and matchings, and notions from measure theory and topology. Results in this area enable one to apply combinatorial techniques to problems in other (seemingly unrelated) branches of mathematics, such as the study of dynamical systems. In this talk I will give an introduction to descriptive combinatorics and discuss some recent progress concerning a particular family of combinatorial tools---the probabilistic method---and its applications in the descriptive setting.