I’ll try and give some background on the definition of knot Floer homology, and perhaps also bordered Heegaard Floer homology if time permits.
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.
‘Koszul duality’ is a phenomenon which algebraists are fond of, and has previously been studied in the context of '(bordered) Heegaard Floer homology' by Lipshitz, Ozsváth and Thurston. In this talk, I shall discuss an occurrence of Koszul duality which links older constructions in Heegaard Floer homology with the bordered Heegaard Floer homology of three-manifolds with torus boundary. I shan’t assume any existing knowledge of Koszul duality or any form of Heegaard Floer homology.
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.
We introduce the notion of tropical curves of hyperelliptic type. These are tropical curves whose Jacobian is isomorphic to that of a hyperelliptic tropical curve, as polarized tropical abelian varieties. Using the tropical Torelli theorem (due to Caporaso and Viviani), this characterization may be phrased in terms of 3-edge connectiviations. We show that being of hyperelliptic type is independent of the edge lengths and is preserved when passing to genus ≥2 connected minors. The main result is an excluded minors characterization of tropical curves of hyperelliptic type.
We study the mean field limit of large stochastic systems of interacting particles. To treat more general and singular kernels, we propose a modulated free energy combination of the method that we had previously developed and of the modulated energy introduced by S. Serfaty. This modulated free energy may be understood as introducing appropriate weights in the relative entropy to cancel the most singular terms involving the divergence of the flow. Our modulated free energy allows to treat singular potentials which combine large smooth part, small attractive singular part and large repulsive singular part. As an example, a full rigorous derivation (with quantitative estimates) of some chemotaxis models, such as Patlak-Keller-Segel system in the subcritical regimes, is obtained. This is a joint work with D. Bresch and Z. Wang.
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.
A graphical model encodes conditional independence relations among random variables. For an undirected graph these conditional independence relations are represented by a simple polytope known as the graph associahedron, which is a Minkowski sum of standard simplices. We prove that there are analogous polytopes for a much larger class of graphical models. We construct this polytope as a Minkowski sum of matroid polytopes. The motivation came from the problem of learning Bayesian networks from observational data. No background on graphical models will be assumed for the talk. This is a joint work with Fatemeh Mohammadi, Caroline Uhler, and Charles Wang.
(This is Part 2, continuation of Tuesday's lecture.)
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.
A real matrix is called orthostochastic if it is the entrywise square of an orthogonal matrix. These matrices have been shown to be deeply connected to determinantal representations of polynomials, and also arise naturally in physics. However, the equations defining the real variety are known only up to the 3x3 case. I will show how various techniques of numerical algebraic geometry give a way of finding (set-theoretic) defining equations for the 4x4 orthostochastic variety, which are smaller (both in number and degree) than the naive equations one might initially guess. Based on joint work with Papri Dey.
Brascamp-Lieb inequalities are estimates for certain multilinear forms on functions on Euclidean spaces. They generalize several classical inequalities, such as Hoelder's inequality or Young's convolution inequality. In this talk we consider singular Brascamp-Lieb inequalities, which arise when one of the functions in the Brascamp-Lieb inequality is replaced by a singular integral kernel. Examples include multilinear singular integral forms such as paraproducts or the multilinear Hilbert transform. We survey some results in the area.
The emergent shape of a knitted fabric is highly sensitive to the underlying stitch pattern. Here, by a stitch pattern we mean a periodic array of symbols encoding a set of rules or instructions performed to produce a swatch or a piece of fabric. So, it is crucial to understand what exactly these instructions mean in terms of mechanical moves performed using a yarn (a smooth piece of string) and a set of knitting needles (oriented sticks). Motivated by the fact that locally every knitting move results in a slip knot, we use tools from topology to model the set of all doubly periodic stitch patterns, knittable & non-knittable, as knots & links in a three manifold. Specifically, we define a map from the set of doubly-periodic stitch patterns to the set of links in S^3 and use link invariants such as the linking number, multivariable Alexander polynomial etc. to characterize them. We focus on such links derived from knitted stitch patterns in an attempt to tackle the question: whether or not a given stitch pattern can be realized through knitting.
We will discuss a novel approach to obtaining non-asymptotic estimates on the lower tail of the least singular value of an $n \times n$ random matrix $M_{n} := M + N_{n}$, where $M$ is a fixed matrix with operator norm at most $O(\exp(n^{c}))$ and $N_n$ is a random matrix, each of whose entries is an independent copy of a random variable with mean 0 and variance 1. This has been previously considered in a series of works by Tao and Vu, and our results improve upon theirs in two ways:
(i) We are able to deal with $\|M\| = O(\exp(n^{c}))$ whereas previous work was applicable for $\|M\| = O(\poly(n))$.
(ii) Even for $\|M\| = O(poly(n))$, we are able to extract more refined information – for instance, our results show that for such $M$, the probability that $M_n$ is singular is $O(exp(-n^{c}))$, whereas even in the case when $N_n$ is an i.i.d. Bernoulli matrix, the results of Tao and Vu only give inverse polynomial singularity probability.
When Alice wants to send a k-bits message v to Bob over a noisy channel, she encodes it as a longer n-bits message Mv, where M is a n times k matrix over F_2. The minimal distance d_M of the linear code M is defined as the minimum Hamming distance between Mw and Mu over all distinct points w,u in F_2^k. In this way, if there are less than d_M/2 corrupted bits in the message, Bob can recover the original message via a nearest neighbor search algorithm.
The classical Gilbert-Varshamov Bound provides a lower bound for d_M if the columns of M are independent copies of X, where X is the random vector uniformly distributed on F_2^n. Under the same assumption on M, we show that the distribution of d_M is essentially the same as the minimum of Hamming weight (Hamming distance to origin) of 2^k-1 i.i.d copies of X.
The result is surprising since M is only generated by k independent copies of X. Furthermore, our results also work for arbitrary finite fields.
This is joint work with Jing Hao, Galyna Livshyts, Konstantin Tikhomirov.
I will talk about algorithms (with unlimited computational power) which adaptively probe pairs of vertices of a graph to learn the presence or absence of edges and whose goal is to output a large clique. I will focus on the case of the random graph G(n,1/2), in which case the size of the largest clique is roughly 2\log(n). Our main result shows that if the number of pairs queried is linear in n and adaptivity is restricted to finitely many rounds, then the largest clique cannot be found; more precisely, no algorithm can find a clique larger than c\log(n) where c < 2 is an explicit constant. I will also discuss this question in the planted clique model. This is based on joint works with Uriel Feige, David Gamarnik, Joe Neeman, Benjamin Schiffer, and Prasad Tetali.
