Georgia Institute of Technology College of Sciences

A fundamental tool used in sampling, counting, and inference problems is the Markov Chain Monte Carlo method, which uses random walks to solve computational problems. The main parameter defining the efficiency of this method is how quickly the random walk mixes (converges to the stationary distribution). The goal of these talks is to introduce a new approach for analyzing the mixing time of random walks on high-dimensional discrete objects. This approach works by directly relating the mixing time to analytic properties of a certain multivariate generating polynomial. As our main application we will analyze basis-exchange random walks on the set of bases of a matroid. We will show that the corresponding multivariate polynomial is log-concave over the positive orthant, and use this property to show three progressively improving mixing time bounds: For a matroid of rank r on a ground set of n elements:

- We will first show a mixing time of O(r^2 log n) by analyzing the spectral gap of the random walk (based on related works on high-dimensional expanders).

- Then we will show a mixing time of O(r log r + r log log n) based on the modified log-sobolev inequality (MLSI), due to Cryan, Guo, Mousa.

- We will then completely remove the dependence on n, and show the tight mixing time of O(r log r), by appealing to variants of well-studied notions in discrete convexity.

Time-permitting, I will discuss further recent developments, including relaxed notions of log-concavity of a polynomial, and applications to further sampling/counting problems.

Based on joint works with Kuikui Liu, Shayan OveisGharan, and Cynthia Vinzant.

The Probabilistic Method is a powerful tool for tackling many problems in discrete mathematics and related areas.
Roughly speaking, its basic idea can be described as follows. In order to prove existence of a combinatorial structure with certain properties, we construct an appropriate probability space, and show that a randomly chosen element of this space has the desired property with positive probability.
In this talk we shall give a gentle introduction to the Probabilistic Method, with an emphasis on examples.

The analysis and decomposition of nonstationary and nonlinear signals in the quest for the identification
of hidden quasiperiodicities and trends is of high theoretical and applied interest nowadays.

Linear techniques like Fourier and Wavelet Transform, historically used in signal processing, cannot capture
completely nonlinear and non stationary phenomena.

For this reason in the last few years new nonlinear methods have been developed like the groundbreaking
Empirical Mode Decomposition algorithm, aka Hilbert--Huang Transform, and the Iterative Filtering technique.

In this seminar I will give an overview of this kind of methods and I will introduce two new algorithms,
the Fast Iterative Filtering and the Adaptive Local Iterative Filtering. I will review the main theoretical results
and outline the most intriguing open problems that still need to be tackled in the field.
Some examples of applications of these techniques to both artificial and real life signals
will be shown to give a foretaste of their potential and robustness.
 

I’ll try and give some background on the definition of knot Floer homology, and perhaps also bordered Heegaard Floer homology if time permits.