- You are here:
- GT Home
- Home
- News & Events

Series: Stochastics Seminar

I will talk about the structure of large square random matrices with centered i.i.d. heavy-tailed entries (only two finite moments are assumed). In our previous work with R. Vershynin we have shown that the operator norm of such matrix A can be reduced to the optimal sqrt(n)-order with high probability by zeroing out a small submatrix of A, but did not describe the structure of this "bad" submatrix, nor provide a constructive way to find it. Now we can give a very simple description of this small "bad" subset: it is enough to zero out a small fraction of the rows and columns of A with largest L2 norms to bring its operator norm to the almost optimal sqrt(loglog(n)*n)-order, under additional assumption that the entries of A are symmetrically distributed. As a corollary, one can also obtain a constructive procedure to find a small submatrix of A that one can zero out to achieve the same regularization.

Im am planning to discuss some details of the proof, the main component of which is the development of techniques that extend constructive regularization approaches known for the Bernoulli matrices (from the works of Feige and Ofek, and Le, Levina and Vershynin) to the considerably broader class of heavy-tailed random matrices.

Series: Graph Theory Seminar

Reed

and Wood and independently Norine, Seymour, Thomas, and Wollan showed

that for each $t$ there is $c(t)$ such that every graph on $n$ vertices

with no $K_t$ minor has

at most $c(t)n$ cliques. Wood asked in 2007 if

$c(t)<c^t$ for some absolute constant $c$. This problem was recently

solved by Lee and Oum. In this paper, we determine the exponential

constant. We prove that every graph on $n$ vertices

with no $K_t$ minor has at most $3^{2t/3+o(t)}n$ cliques. This bound is tight for $n \geq 4t/3$.

We use the similiar idea to give an upper bound on the number of cliques in

an $n$-vertex graph with no $K_t$-subdivsion. Easy computation will

give an upper

bound of $2^{3t+o(t)}n$; a more careful examination gives an upper bound

of $2^{1.48t+o(t)}n$. We conjecture that the optimal exponential

constant is $3^{2/3}$ as in the case of minors.

This is a joint work with Jacob Fox.

Series: School of Mathematics Colloquium

The Remez inequality for polynomials quantifies the way the maximum of a polynomial over an interval is controlled by its maximum over a subset of positive measure. The coefficient in the inequality depends on the degree of the polynomial; the result also holds in higher dimensions. We give a version of the Remez inequality for solutions of second order linear elliptic PDEs and their gradients. In this context, the degree of a polynomial is replaced by the Almgren frequency of a solution. We discuss other results on quantitative unique continuation for solutions of elliptic PDEs and their gradients and give some applications for the estimates of eigenfunctions for the Laplace-Beltrami operator. The talk is based on a joint work with A. Logunov.

Series: Stochastics Seminar

One of the most famous methods for solving large-scale over-determined linear systems is Kaczmarz algorithm, which iteratively projects the previous approximation x_k onto the solution spaces of the next equation in the system. An elegant proof of the exponential convergence of this method using correct randomization of the process is due to Strohmer and Vershynin (2009). Many extensions and generalizations of the method were proposed since then, including the works of Needell, Tropp, Ward, Srebro, Tan and many others. An interesting unifying view on a number of iterative solvers (including several versions of the Kaczmarz algorithm) was proposed by Gower and Richtarik in 2016. The main idea of their sketch-and-project framework is the following: one can observe that the random selection of a row (or a row block) can be represented as a sketch, that is, left multiplication by a random vector (or a matrix), thereby pre-processing every iteration of the method, which is represented by a projection onto the image of the sketch.

I will give an overview of some of these methods, and talk about the role that random matrix theory plays in the showing their convergence. I will also discuss our new results with Deanna Needell on the block Gaussian sketch and project method.

Series: High Dimensional Seminar

One of the most famous methods for solving large-scale over-determined linear systems is Kaczmarz algorithm, which iteratively projects the previous approximation x_k onto the solution spaces of the next equation in the system. An elegant proof of the exponential convergence of this method using correct randomization of the process is due to Strohmer and Vershynin (2009). Many extensions and generalizations of the method were proposed since then, including the works of Needell, Tropp, Ward, Srebro, Tan and many others. An interesting unifying view on a number of iterative solvers (including several versions of the Kaczmarz algorithm) was proposed by Gower and Richtarik in 2016. The main idea of their sketch-and-project framework is the following: one can observe that the random selection of a row (or a row block) can be represented as a sketch, that is, left multiplication by a random vector (or a matrix), thereby pre-processing every iteration of the method, which is represented by a projection onto the image of the sketch.

I will give an overview of some of these methods, and talk about the role that random matrix theory plays in the showing their convergence. I will also discuss our new results with Deanna Needell on the block Gaussian sketch and project method.

Series: Analysis Seminar

Many problems of spherical discrete and metric geometry may be reformulated as energy minimization problems and require techniques that stem from harmonic analysis, potential theory, optimization etc. We shall discuss several such problems as well of applications of these ideas to combinatorial geometry, discrepancy theory, signal processing etc.

Series: Mathematical Biology Seminar

The likelihood of HIV infection following risky contact is believed to be low. This suggests that the infection process is stochastic and governed by rare events. I will present mathematical branching process models of early infection and show how we have used them to gain insights into the duration of the undetectable phase of HIV infection, the likelihood of success of pre- and post-exposure prophylaxis, and the effects of prior infection with HSV-2. Although I will describe quite a bit of theory, I will try to keep giant and incomprehensible formulae to a minimum.

Series: Geometry Topology Seminar

Series: Geometry Topology Seminar

Khovanov homology and knot Floer homology are two knot invariants which are defined using very different techniques, with Khovanov homology having its roots in representation theory and knot Floer homology in symplectic geometry. However, they seem to contain a lot of the same topological data about knots. Rasmussen conjectured that this similarity stems from a spectral sequence from Khovanov homology to knot Floer homology. In this talk I will give a construction of this spectral sequence. The construction utilizes a recently defined knot homology theory HFK_2 which provides a framework in which the two theories can be related.

Series: Algebra Seminar

If a finite group $G$ acts on a Cohen-Macaulay ring $A$, and the order of $G$ is a unit in $A$, then the invariant ring $A^G$ is Cohen-Macaulay as well, by the Hochster-Eagon theorem. On the other hand, if the order of $G$ is not a unit in $A$ then the Cohen-Macaulayness of $A^G$ is a delicate question that has attracted research attention over the last several decades, with answers in several special cases but little general theory. In this talk we show that the statement that $A^G$ is Cohen-Macaulay is equivalent to a statement quantified over the inertia groups for the action of G$ on $A$ acting on strict henselizations of appropriate localizations of $A$. In a case of long-standing interest—a permutation group acting on a polynomial ring—we show how this can be applied to find an obstruction to Cohen-Macaulayness that allows us to completely characterize the permutation groups whose invariant ring is Cohen-Macaulay regardless of the ground field. This is joint work with Sophie Marques.