Seminars and Colloquia by Series

Understanding statistical-vs-computational tradeoffs via the low-degree likelihood ratio

Series
Stochastics Seminar
Time
Thursday, October 17, 2019 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Alex WeinNew York University

High-dimensional inference problems such as sparse PCA and planted clique often exhibit statistical-vs-computational tradeoffs whereby there is no known polynomial-time algorithm matching the performance of the optimal estimator. I will discuss an emerging framework -- based on the so-called low-degree likelihood ratio -- for precisely predicting these tradeoffs and giving rigorous evidence for computational hardness in the conjectured hard regime. This method was originally proposed in a sequence of works on the sum-of-squares hierarchy, and the key idea is to study whether or not there exists a low-degree polynomial that succeeds at a given statistical task.

In the second part of the talk, I will give an application to the algorithmic problem of finding an approximate ground state of the SK (Sherrington-Kirkpatrick) spin glass model. I will explain two variants of this problem: "optimization" and "certification." While optimization can be solved in polynomial time [Montanari'18], we give rigorous evidence (in the low-degree framework) that certification cannot be. This result reveals a fundamental discrepancy between two classes of algorithms: local search succeeds while convex relaxations fail.

Based on joint work with Afonso Bandeira and Tim Kunisky (https://arxiv.org/abs/1902.07324 and https://arxiv.org/abs/1907.11636).

Regularity Decompositions for Sparse Pseudorandom Graphs

Series
High Dimensional Seminar
Time
Wednesday, October 16, 2019 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Gregory M BodwinGeorgia Tech

 A powerful method for analyzing graphs is to first apply regularity lemmas, which roughly state that one can partition the graph into a few parts so that it looks mostly random between the parts, and then apply probabilistic tools from there.  The drawback of this approach is that it only works in general when the input graph is very dense: standard regularity lemmas are trivial already for n-node graphs on "only" <= n^{1.99} edges.

In this work we prove extensions of several standard regularity lemmas to sparse graphs, which are nontrivial so long as the graph spectrum is not too far from that of a random graph.  We then apply our notion of "spectral pseudorandomness" to port several notable regularity-based results in combinatorics and theoretical computer science down to sparser graphs.

 

Joint work with Santosh Vempala.

 

The moduli space of matroids

Series
Algebra Seminar
Time
Wednesday, October 16, 2019 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Oliver LorscheidInstituto Nacional de Matematica Pura e Aplicada (IMPA)

Matroids are combinatorial gadgets that reflect properties of linear algebra in situations where this latter theory is not available. This analogy prescribes that the moduli space of matroids should be a Grassmannian over a suitable base object, which cannot be a field or a ring; in consequence usual algebraic geometry does not provide a suitable framework. In joint work with Matt Baker, we use algebraic geometry over F1, the so-called field with one element, to construct such moduli spaces. As an application, we streamline various results of matroid theory and find simplified proofs of classical theorems, such as the fact that a matroid is regular if and only if it is binary and orientable.

We will dedicate the first half of this talk to an introduction of matroids and their generalizations. Then we will outline how to use F1-geometry to construct the moduli space of matroids. In a last part, we will explain why this theory is so useful to simplify classical results in matroid theory.

Partial Torelli Groups

Series
Geometry Topology Student Seminar
Time
Wednesday, October 16, 2019 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Daniel MinahanGeorgia Tech

The Torelli group is the subgroup of the mapping class group acting trivially on homology.  We will discuss some basic properties of the Torelli group and explain how to define it for surfaces with boundary.  We will also give some Torelli analogues of the Birman exact sequence.

Effect of non-conservative perturbations on homoclinic and heteroclinic orbits

Series
CDSNS Colloquium
Time
Wednesday, October 16, 2019 - 11:15 for 1 hour (actually 50 minutes)
Location
Skiles 05
Speaker
Marian GideaYeshiva University
he motivation of this work comes from astrodynamics. Consider a spacecraft traveling  between the Earth and the Moon. Assume that the spacecraft follows a zero-cost orbit  by coasting along the hyperbolic invariant manifolds associated to periodic orbits near the equilibrium points, at some fixed energy level. We want to make a maneuver -- impulsive or low thrust --  in order  to jump to the hyperbolic invariant manifold  corresponding to a different energy level. Mathematically, turning on the thrusters amounts to a adding a small, non-conservative, time-dependent perturbation to the original system. Given such an explicit perturbation, we would like to  estimate its effect on the orbit of the spacecraft.
 
We study this question in the context of two simple models: the pendulum-rotator system, and the planar circular restricted three-body problem. Homoclinic/heteroclinic excursions can be described via the scattering map, which gives the future asymptotics of an orbit as a function of the past asymptotics. We add a time-dependent, non-conservative perturbation, and provide explicit formulas, in terms of convergent integrals, for the perturbed scattering map.

Host metapopulation, disease epidemiology and host evolution

Series
Mathematical Biology Seminar
Time
Wednesday, October 16, 2019 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Jing JiaoNIMBioS - University of Tennessee

While most evolutionary studies of host-pathogen dynamics consider pathogen evolution alone or host-pathogen coevolution, for some diseases (e.g., White Nose syndrome in bats), there is evidence that hosts can sometimes evolve more rapidly than their pathogen. In this talk, we will discuss the spatial, temporal, and epidemiological factors may drive the evolutionary dynamics of the host population. We consider a simplified system of two host genotypes that trade off factors of disease robustness and spatial mobility or growth. For diseases that infect hosts for life, we find that migration and disease-driven mortality can have antagonistic effect on host densities when disease selection on hosts is low, but show synergy when selection is high. For diseases that allow hosts to recover with immunity, we explore the conditions under which the disease dies out, becomes endemic, or has periodic outbreaks, and show how these dynamics relate to the relative success of the robust and wild type hosts in the population over time. Overall, we will discuss how combinations of host spatial structure, demography, and epidemiology of infectious disease can significantly influence host evolution and disease prevalence. We will conclude with some profound implications for wildlife conservation and zoonotic disease control.

Mordell-Weil rank jumps and the Hilbert property

Series
Algebra Seminar
Time
Wednesday, October 16, 2019 - 10:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Cecília SalgadoUniversidade Federal do Rio de Janeiro

Let X be an elliptic surface with a section defined over a number field. Specialization theorems by Néron and Silverman imply that the rank of the Mordell-Weil group of special fibers is at least equal to the MW rank of the generic fiber. We say that the rank jumps when the former is strictly large than the latter. In this talk, I will discuss rank jumps for elliptic surfaces fibred over the projective line. If the surface admits a conic bundle we show that the subset of the line for which the rank jumps is not thin in the sense of Serre. This is joint work with Dan Loughran.

Fall recess

Series
Algebra Seminar
Time
Tuesday, October 15, 2019 - 13:30 for 1 hour (actually 50 minutes)
Location
Speaker
No seminar.

Tangles and approximate packing-covering duality

Series
Graph Theory Working Seminar
Time
Thursday, October 10, 2019 - 16:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Youngho YooGeorgia Tech

 Tangles capture a notion of high-connectivity in graphs which differs from $k$-connectivity. Instead of requiring that a small vertex set $X$ does not disconnect the graph $G$, a tangle “points” to the connected component of $G-X$ that contains most of the “highly connected part”. Developed initially by Robertson and Seymour in the graph minors project, tangles have proven to be a fundamental tool in studying the general structure of graphs and matroids. Tangles are also useful in proving that certain families of graphs satisfy an approximate packing-covering duality, also known as the Erd\H{o}s-P\'osa property. In this talk I will give a gentle introduction to tangles and describe some basic applications related to the Erd\H{o}s-P\'osa property.

 

Pages