Graduate Thesis Defenses 2018

Renee Bell

Title: Local-to-Global Extensions for Wildly Ramified Covers of Curves
Date: Friday, April 27, 2018 | 3:30pm | Room: 2-361
Committee: Bjorn Poonen (thesis advisor), Andrew Sutherland, Davesh Maulik

Abstract

Given a Galois cover of curves $X \to Y$ with Galois group $G$ which is totally ramified at a point $x$ and unramified elsewhere, restriction to the punctured formal neighborhood of $x$ induces a Galois extension of Laurent series rings $k((u))/k((t))$. If we fix a base curve $Y$, we can ask when a Galois extension of Laurent series rings comes from a global cover of $Y$ in this way. Harbater proved that over a separably closed field, every Laurent series extension comes from a global cover for any base curve if $G$ is a $p$-group, and he gave a condition for the uniqueness of such an extension. Using a generalization of Artin--Schreier theory to non-abelian $p$-groups, we characterize the curves $Y$ for which this extension property holds and for which it is unique up to isomorphism, but over a more general ground field.

Eva Belmont

Title: Localization at $b_{10}$ in the stable category of comodules over the Steenrod reduced powers
Date: Monday, April 30, 2018 | 4:30pm | Room: 2-131
Committee: Haynes Miller (chair), Goncalo Tabuada, Zhouli Xu

Abstract

Chromatic localization can be seen as a way to calculate a particular infinite piece of the homotopy of a spectrum. For example, the (finite) chromatic localization of a p-local sphere is its rationalization, and the corresponding chromatic localization of its Adams $E_2$ page recovers just the zero-stem. We study a different localization of Adams $E_2$ pages for spectra, which recovers more information than the chromatic localization. This approach can be seen as the analogue of chromatic localization in a category related to the derived category of comodules over the dual Steenrod algebra, a setting in which Palmieri has developed an analogue of chromatic homotopy theory. In this thesis, we work at the prime 3 and compute the $E_2$ page and first nontrivial differential of a spectral sequence converging to $b_{10}^{-1}Ext_P^*(F_3, F_3)$, which agrees with a direct summand of the Adams $E_2$ term for the sphere above a line of slope 1/23, and give a complete calculation of other localized Ext groups, including $b_{10}^{-1}Ext_P^*(F_3, F_3[\xi_1^3])$.

David Corwin

Title: Generalized Obstructions to the Local-Global Principle and Motivic non-Abelian Chabauty's Method for the Projective Line Minus Three Points
Date: Monday, April 30, 2018 | 3:00pm | Room: 2-139
Committee: Bjorn Poonen (thesis advisor), Wei Zhang, Davesh Maulik

Abstract

This thesis studies two cases in which cohomological invariants are used to obstruct the existence of rational and integral points on varieties.

The first concerns the $S$-unit equation, which asks for solutions to $x+y=1$ with $x$ and $y$ both $S$-units, or units in $Z=\mathbb{Z}[1/S]$. This is equivalent to finding the set of $Z$-points of $\mathbb{P}^1 \setminus \{0,1,\infty\}$. We follow work of Dan-Cohen--Wewers and Brown in applying a motivic version of the non-abelian Chabauty's method of Minhyong Kim to find polynomials in $p$-adic polylogarithms that vanish on this set of integral points. More specifically, we extend the computations already done by Dan-Cohen--Wewers to the integer ring $\mathbb{Z}[1/3]$, and we provide some significant simplifications to a previous algorithm of Dan-Cohen, especially in the case of $\mathbb{Z}[1/S]$. One of the reasons for doing this is to verify cases of Kim's conjecture, which states that these $p$-adic functions precisely cut out the set of integral points. This is joint work with Ishai Dan-Cohen.

The second is about obstructions to the local-global principle. The étale Brauer-Manin obstruction of Skorobogatov can be used to explain the failure of the local-global principle for many algebraic varieties. In 2010, Poonen gave the first example of failure of the local-global principle that cannot be explained by the étale Brauer-Manin obstruction. Further obstructions such as the étale homotopy obstruction and the descent obstruction are unfortunately equivalent to the étale Brauer-Manin obstruction. However, Poonen's construction was not accompanied by a definition of a new, finer obstruction. Here, we present a possible definition for such an obstruction by applying the Brauer-Manin obstruction to each piece of every stratification of the variety. We prove that this obstruction is necessary and sufficient, over imaginary quadratic fields and totally real fields unconditionally, and over all number fields conditionally on the section conjecture. This is part of a joint project with Tomer Schlank.

In this defense, we will focus on the first.

Evgeni Dimitrov

Title: Scaling limits of random plane partitions and six-vertex models
Date: Thursday, April 19, 2018 | 2:30pm | Room: 4-153
Committee: Alexei Borodin, Leonid Petrov, Vadim Gorin

Abstract

We present a collection of results about the scaling limits of several models from integrable probability.

Our first result concerns the asymptotic behavior of the bottom slice of a Hall-Littlewood random plane partition. We show the latter concentrates around a limit shape and in two different scaling regimes identify the fluctuations around this shape with the GUE Tracy-Widom distribution and the narrow wedge initial data solution to the Kardar-Parisi-Zhang (KPZ) equation. The second result concerns the limiting behavior of a class of six-vertex models in the quadrant, and we obtain the GUE-corners process as a scaling limit for this class near the boundary. Our final result, joint with Ivan Corwin, demonstrates the (long predicted) transversal 2/3 critical exponent for the height functions of the stochastic six-vertex model and asymmetric simple exclusion process (ASEP).

The algebraic parts of our arguments involve the construction and use of degenerations and modifications of the Macdonald difference operators to obtain rich families of observables for the models we consider. These formulas are in terms of multiple contour integrals and provide a direct access to quantities of interest. The analytic parts of our arguments include the detailed asymptotic analysis of Fredholm determinants and contour integrals through steepest descent methods. An important aspect of our approach, is the combination of exact formulas with more probabilistic arguments, based on various Gibbs properties enjoyed by the models we study.

Sam Elder

Title: Reliable Validation: New Perspectives on Adaptive Data Analysis and Cross-Validation
Date: Tuesday, August 7, 2018 | 3:00pm | Room: 4-149
Committee: Jon Kelner, Tamara Broderick, Philippe Rigollet

Abstract

Validation refers to the challenge of assessing how well a learning algorithm performs after it has been trained on a given data set. It forms an important step in machine learning, as such assessments are then used to compare and choose between algorithms and provide reasonable approximations of their accuracy.

In this thesis, we provide new approaches for addressing two common problems with validation. In the first half, we assume a simple validation framework, the holdout set, and address an important question of how many algorithms can be accurately assessed using the same holdout set, in the particular case where these algorithms are chosen adaptively. We do so by first critiquing the initial approaches to building a theory of adaptivity, then offering an alternative approach and preliminary results within this approach, all geared towards characterizing the inherent challenge of adaptivity.

In the second half, we address the validation framework itself. Most common practice does not just use a single holdout set, but averages results from several, a family of techniques known as cross-validation. In this work, we offer several new cross-validation techniques with the common theme of utilizing training sets of varying sizes. This culminates in hierarchical cross-validation, a meta-technique for using cross-validation to choose the best cross-validation method.

Title: Active flows and networks
Date: Wednesday, April 25, 2018 | 2:00pm | Room: 2-361
Committee: Jörn Dunkel, Ruben Rosales, Jeremy England

Abstract

Coherent, large scale dynamics in many nonequilibrium physical, biological, or information transport networks are driven by small-scale local energy input. In the first part of this thesis, we introduce and explore two analytically tractable nonlinear models for such active flow networks, drawing motivation from recent microfluidic experiments on bacterial and other microbial suspensions. In contrast to equipartition with thermal driving, we find that active friction selects discrete states with only a limited number of modes excited at distinct fixed amplitudes. When the active transport network is incompressible, these modes are cycles with constant flow; when it is compressible, they are oscillatory. As is common in such network dynamical systems, the spectrum of the underlying graph Laplacian plays a key role in controlling the flow. Spectral graph theory has traditionally prioritized analyzing Laplacians of unweighted networks with specified adjacency properties. For the second part of the thesis, we introduce a complementary framework, providing a mathematically rigorous positively weighted graph construction that exactly realizes any desired spectrum. We illustrate the broad applicability of this approach by showing how designer spectra can be used to control the dynamics of three archetypal physical systems. Specifically, we demonstrate that a strategically placed gap induces weak chimera states in Kuramoto-type oscillator networks, tunes or suppresses pattern formation in a generic Swift-Hohenberg model, and leads to persistent localization in a discrete Gross-Pitaevskii quantum network.

Sherry Gong

Title: Results on Spectral Sequences for Monopole and Singular Instanton Floer Homologies
Date: Friday, April 27, 2018 | 2:00pm | Room: 2-361
Committee: Tomasz Mrowka, Victor Guillemin, Matthew Stoffregen

Abstract

We study two gauge-theoretic Floer homologies associated to links, the singular instanton Floer homology and the monopole Floer homolog. For both cases, we study in particular the spectral sequence that relates the Floer homologies to the Khovanov homologies of links.

In our study of singular instanton Floer homology, we introduce a version of Khovanov homology for alternating links with marking data, $\omega$, inspired by singular instanton theory. We show that the analogue of the spectral sequence from Khovanov homology to singular instanton homology for this marked Khovanov homology collapses on the $E_2$ page for alternating links. We moreover show that for non-split links the Khovanov homology we introduce for alternating links does not depend on $\omega$; thus, the instanton homology also does not depend on $\omega$ for non-split alternating links. We study a version of binary dihedral representations for links with markings, and show that for links of non-zero determinant, this also does not depend on $\omega$.

In our study of monopole Floer homology, we construct families of metrics on the cobordisms that are used to construct differentials in the spectral sequence relating the Khovanov homology of a link to the monopole Floer homology of its double branched cover such that each metric has positive scalar curvature. This allows us to conclude that the Seiberg-Witten equations for these families of metrics have no irreducible solutions, so the differentials in the spectral sequence can be computed from counting only the reducible solutions.

Ewain Gwynne

Title: On the metric structure of random planar maps and SLE-decorated Liouville quantum gravity
Date: Thursday, April 5, 2018 | 1:00pm | Room: 2-255
Committee: Scott Sheffield, Vadim Gorin, and Stephane Benoist

Abstract

A random planar map is a graph embedded in the sphere, viewed modulo orientation-preserving homeomorphisms. Random planar maps are the discrete analogues of continuum random surfaces called $\gamma$-Liouville quantum gravity (LQG) surfaces with parameter $\gamma \in (0,2]$.

We study the large-scale structure of random planar maps (and statistical mechanics models on them) viewed as metric measure spaces equipped with the graph distance and the counting measure on vertices.

In particular, we show that uniform random planar maps (which correspond to the case $\gamma=\sqrt{8/3}$) decorated by a self-avoiding walk or a critical percolation interface converge in the scaling limit to $\sqrt{8/3}$-LQG surfaces decorated by SLE$_{8/3}$ and SLE$_6$, respectively, with respect to a generalization of the Gromov-Hausdorff topology.

We also introduce an approach for analyzing certain random planar maps belonging to the $\gamma$-LQG universality class for general $\gamma \in (0,2)$ and use this approach to prove several estimates for graph distances in such maps.

Title: Closed Quasigeodesics, Escaping from Polygons, and Conflict-Free Graph Coloring
Date: Monday, April 30, 2018 | 3:00pm | Room: 2-147
Committee: Professors Demaine (CS), Michael Sipser, and Lawrence Guth

Abstract

Closed quasigeodesics

A closed quasigeodesic on the surface of a polyhedron is a loop which can everywhere locally be unfolded to a straight line: that is, straight on faces, uniquely determined on edges, and with as much flexibility at a vertex as that vertex's curvature. On any convex polyhedron, at least three of these are known to exist, by a nonconstructive topological proof. We present an algorithm to find one in time $O(n^2\epsilon^{-2}L\ell^{-1})$, where $\epsilon$ is the minimum curvature of a vertex, and $L$ and $\ell$ are the greatest and least sidelengths, respectively.

Escaping from polygons

You move continuously at speed 1 in the interior of a polygon $P$, trying to reach the boundary. Outside it, a zombie moves continuously at speed $r$, trying to be at the boundary when you reach it. For what $r$ can you escape and for what $r$ can the zombie catch you? We give exact results for some $P$, a simple approximation to within a factor of roughly $9.2504$, an approximation algorithm, and NP-hardness and hardness of approximation results for related problems.

Conflict-free graph coloring

A conflict-free $k$-coloring of a graph assigns one of $k$ different colors to some of the vertices such that, for every vertex $v$, there is a color that is assigned to exactly one vertex among $v$ and $v$'s neighbors. We study the natural problem of the conflict-free chromatic number $\chi_{CF}(G)$ (the smallest $k$ for which conflict-free $k$-colorings exist), with a focus on planar graphs.

For general graphs, we provide a sufficient condition for the existence of a conflict-free coloring, corresponding to a conflict-free variant of the Hadwiger Conjecture: if $G$ does not contain $K_{k+1}$ as a minor, then $\chi_{CF}(G) \leq k$. For planar graphs, we obtain a tight worst-case bound: three colors are sometimes necessary and always sufficient. In addition, we give a complete characterization of the algorithmic/computational complexity of conflict-free coloring. It is NP-complete to decide whether a planar graph has a conflict-free coloring with one color, while for outerplanar graphs, this can be decided in polynomial time. Furthermore, it is NP-complete to decide whether a planar graph has a conflict-free coloring with two colors, while for outerplanar graphs, two colors always suffice.

Nina Holden

Title: Conformal embedding of random planar maps and Hausdorff dimensions for Schramm-Loewner evolutions
Date: Thursday, April 12, 2018 | 4:00pm | Room: 2-449
Committee: Scott Sheffield, Alexei Borodin, and Stephane Benoist

Abstract

The Schramm-Loewner evolution (SLE) is a random fractal curve which describes the scaling limit of interfaces in a wide range of statistical physics models. Liouville quantum gravity (LQG) is a random fractal surface which arises as the scaling limit of discrete surfaces known as random planar maps (RPM). In the first part of the thesis we prove a KPZ-type formula, which we use to give new and very short proofs for the Hausdorff dimension of certain subsets of SLE curves. In the second part of the thesis we prove scaling limit results for uniformly sampled RPM known as triangulations. First we prove a scaling limit result for a number of observables of critical site percolation on the triangulation, and then we prove that the triangulation converges to LQG under an explicit conformal embedding into the complex plane.

Sam Hopkins

Title: Root system chip-firing
Date: Friday, April 27th, 2018 | 10:00am | Room: 2-361
Committee: Prof. Alexander Postnikov (Chair and thesis advisor, MIT), Prof. Richard Stanley (MIT), Prof. James Propp (UMass, Lowell)

Abstract

This thesis investigates an extension of the classical chip-firing game to “other Cartan-Killing types.” The chip-firing process is a discrete dynamical system whose states are configurations of chips on the vertices of a graph and whose the transition moves are firings whereby a vertex with at least as many chips as neighbors may send one chip to each neighbor. A fundamental property of chip-firing is that the process is confluent: from any initial configuration, all sequences of firings lead to the same terminal configuration. Propp recently introduced a labeled chip-firing process for which confluence becomes a subtler question. We prove that labeled chip-firing is confluent starting from an even number of chips at the origin (but not from an odd number). We then reinterpret labeled chip-firing as a process on the weight lattice of a root system, where the firing moves consist of adding a positive root whenever the weight we are at is orthogonal to that root. We call this the central-firing process. We give conjectures about initial weights from which central-firing is confluent. We also prove that central-firing is always confluent from all initial weights if we mod out by the action of the Weyl group.

Then we introduce and study some remarkable deformations of the central-firing process which we call the symmetric and truncated interval-firing processes. These are analogous to the Catalan and Shi hyperplane arrangements. We prove that these interval-firing processes are always confluent from all initial weights. We also show that the number of weights with given interval-firing stabilization is a polynomial in our deformation parameter. We call these polynomials the symmetric and truncated Ehrhart-like polynomials because they are in some ways analogous to the Ehrhart polynomial of a polytope. We conjecture that the Ehrhart-like polynomials have nonnegative integer coefficients, and we prove “half” of this positivity conjecture by providing an explicit, positive formula for the symmetric Ehrhart-like polynomials.

Chiheon Kim

Title: Statistical limits of graphical models and a semidefinite programming approach.
Date:, Tuesday, July 31, 2018 | 3:00pm | Room: 2-255
Committee: Michel X. Goemans (Chair/Advisor), Philippe Rigollet, Afonso S. Bandeira (NYU)

Abstract

Community recovery is one of major problems in data science and computer science. Roughly speaking, the goal in community recovery is to find the hidden clusters from a given relational data, which is often represented as a labelled (hyper)graph where nodes corresponds to items which we would like to label, and edges corresponds to relations between the items. We are interested in statistical models where a data set is generated according to a hidden community structure, with some random noise involved.

Specifically, we investigate the problem of exact recovery in statistical models which can be expressed in terms of a graphical channels. Under a graphical channel model, a ground truth is chosen from a prior distribution which is known to us, and we observe noisy measurements of relation between each k nodes, which are mutually independent and each measurement only depends on true labels of those k nodes. It well generalizes the models such as the stochastic block models and spiked tensor models with additive gaussian noises, which gained much interest over the last few decades.

In this thesis, we investigate the statistical limits of exact recovery in various graphical channel models, and analyze a semidefinite program based algorithm for exact recovery. Regarding the statistical limits, we show that essentially the achievability of exact recovery is determined by whether we can recover the label of one node given all others’ labels. This phenomenon is called local-to-global amplification’’ in a work of Abbe under the setting of the stochastic block model, and we confirm that local-to-global amplification is indeed a general phenomenon for generic graphical channel models. As a corollary, we find the explicit threshold for exact recovery to be achievable.

On the other hand, we consider hypergraph generalization of the stochastic block model and planted bisection model with Gaussian noises. We propose an algorithmic strategy we call truncate-and-relax’’ which is based on a standard semidefinite relaxation of quadratic programming, and show that our algorithms achieve exact recovery in orderwise optimal parameter regimes. We complement our result by showing lower bounds of our algorithm and discuss related open problems of independent interest.

Dongkwan Kim

Title: On total Springer representations
Date: Wednesday, April 18, 2018 | 2:30pm | Room: 2-449
Committee: George Lusztig (chair, thesis supervisor), David Vogan, Pavel Etingof

Abstract

This thesis studies the alternating sum of cohomology groups of a Springer fiber (in characteristic 0), called a total Springer representation, as a representation of both the Weyl group and the stabilizer of the corresponding nilpotent element.

For classical types, we present explicit formulas for the decomposition of total Springer representations into irreducible ones of the corresponding Weyl group using Kostka-Foulkes polynomials. Also, the character value at any element contained in type A maximal parabolic subgroup(s) of the Weyl group is explicitly given in terms of Green polynomials. As a result, closed formulas for the Euler characteristic of Springer fibers are deduced. Our proof relies on analysis of geometry of Springer fibers and combinatorics of symmetric functions. Moreover, we provide formulas for the character value of a total Springer representation at any element in the stabilizer of the corresponding nilpotent element.

For exceptional types, the character values of total Springer representations are completely known. Here, we only describe the decomposition of such representations into irreducible ones of stabilizers of corresponding nilpotent elements.

Eric Larson

Title: The Maximal Rank Conjecture
Date: Thursday, April 5, 2018 | 2:00pm | Room: 4-149
Committee: Joseph Harris, Bjorn Poonen, and Davesh Maulik

Abstract

Let C be a general curve of genus g, embedded in P^r via a general linear series of degree d. In this thesis, we prove the Maximal Rank Conjecture, which determines the Hilbert function of C.

Augustus Lonergan

Title: Power Operations and Central Maps in Representation Theory
Date: Friday, April 27, 2018 | 3:00pm | Room: 2-136
Committee: Roman Bezrukavnikov (chair and advisor), Pavel Etingof, David Vogan

Abstract

Let B be a commutative F_p-algebra and let B_h be a quantization of B. A key favorable property of B_h is that it contains the Frobenius twist of B in its center. In that case we say that B_h is a Frobenius-constant quantization of B (see work of Bezrukavnikov et al.). One large and important class of examples of commutative algebras and their quantizations, known as (quantum) Coulomb branches, was recently defined by Braverman-Finkelberg-Nakajima (motivated by physics). We use Steenrod's construction to show that the quantum Coulomb branch is a Frobenius-constant quantization. This is an application of the general idea that one can approximate an action of the circle by the action of its subgroup C of order p. The key geometric input is a version of the Beilinson-Drinfeld Grassmannian in which the loop-rotation action of C on the affine Grassmannian Gr is deformed to the action of C on Gr^p by cyclic permutations.

Cheng Mao

Title: Matrix Estimation with Latent Permutations
Date: Thursday, March 22, 2018 | 2:00pm | Room: 2-449
Committee: Philippe Rigollet (advisor), Ankur Moitra, Alexander Rakhlin

Abstract

Motivated by various applications such as seriation, network alignment and ranking from pairwise comparisons, we study the problem of estimating a structured matrix with rows and columns shuffled by latent permutations, given noisy and incomplete observations of its entries. This problem is at the intersection of shape constrained estimation which has a long history in statistics, and latent permutation learning which has driven a recent surge of interest in the machine learning community. Shape constraints on matrices, such as monotonicity and smoothness, are generally more robust than parametric assumptions, and often allow for adaptive and efficient estimation in high dimensions. On the other hand, latent permutations underlie many graph matching and assignment problems that are computationally intractable in the worst-case and not yet well-understood in the average-case. Therefore, it is of significant interest to both develop statistical approaches and design efficient algorithms for problems where shape constraints meet latent permutations.

In this work, we consider three specific models: the statistical seriation model, the noisy sorting model and the strong stochastic transitivity model. First, statistical seriation consists in permuting the rows of a noisy matrix in such a way that all its columns are approximately monotone, or more generally, unimodal. We study both global and adaptive rates of estimation for this model, and introduce an efficient algorithm for the monotone case.

Next, we move on to ranking from pairwise comparisons, and consider the noisy sorting model. We establish the minimax rates of estimation for noisy sorting, and propose a near-linear time multistage algorithm that achieves a near-optimal rate.

Finally, we study the strong stochastic transitivity model that significantly generalizes the noisy sorting model for estimation from pairwise comparisons. Our efficient algorithm achieves the rate $\tilde O(n^{-3/4})$, narrowing a gap between the statistically optimal rate $\tilde \Theta(n^{-1})$ and the state-of-the-art computationally efficient rate $\tilde O(n^{-1/2})$. In addition, we consider the scenario where a fixed subset of pairwise comparisons is given. A dichotomy exists between the worst-case design, where consistent estimation is often impossible, and an average-case design, where we show that the optimal rate of estimation depends on the degree sequence of the comparison topology.

Andrew Rzeznik

Title: Applied math in geophysical fluids: leaky mode expansions for partially trapped wave problems and mining plumes
Date: Tuesday, August 7, 2018 | 4:00pm | Room: 2-361
Committee: Rodolfo Ruben Rodolfo Rosales, Prof. of Applied Mathematics Jörn Dunkel, Associate Prof. of Applied Mathematics Esteban Tabak, Professor of Mathematics, New York University Courant Institute of Mathematical Sciences

Abstract

The first portion of this work focuses on leaky modes in the atmospheric sciences. Leaky modes (related to quasimodes, scattering resonances, and the singularity expansion method) are discrete, oscillatory and decaying modes that arise in conservative systems where waves are partially trapped locally. By replacing the infinite domain with a finite domain and appropriate boundary conditions it is possible in many cases to construct a complete basis for the solution in terms of these modes. Formulating such effective boundary conditions requires a notion of the direction of propagation of the waves. For this purpose we introduce a generalization of the concept of group speed for exponentially decaying but conservative waves. This is found via an extended modulation argument and a generalization of Whitham's Average Lagrangian theory. The theory shows a close relationship exists between the branch cuts of the dispersion relation and the propagation direction, and is used to create spectral decompositions for simple problems in internal gravity waves.

The last chapter considers deep-sea nodule mining operations which potentially involve plans for discharge plumes to be released into the water column by surface operation vessels. We consider the effects of non-uniform, realistic stratifications with vertical shear on forced compressible plumes. The plume model is developed to account for the influence of thermal conduction through the discharge pipe and an initial adjustment phase. We investigate the substantial role of compressibility, for which a dimensionless number is introduced to determine its importance compared to that of the background stratification. Our results show that (i) small-scale stratification features can have a significant impact, (ii) in a static ambient there is a discharge flow rate that minimizes the plume vertical extent, (iii) the ambient velocity profile plays an important role in determining final plume scale and dilution factor, and (iv) for a typical plume the dilution factor is expected to be several hundred to a thousand.

David Rolnick

Title: Towards an Integrated Understanding of Neural Networks
Date: Tuesday, April 24, 2018 | 4:00pm | Room: 32-124
Committee: Nir Shavit (primary thesis advisor), Ed Boyden, Max Tegmark, Ankur Moitra, Jonathan Kelner

Abstract

Neural networks underpin both biological intelligence and modern AI systems, yet there is relatively little theory for how the observed behavior of these networks arises. Even the connectivity of neurons within the brain remains largely unknown, and popular deep learning algorithms lack theoretical justification or reliability guarantees. This thesis aims towards a more rigorous understanding of neural networks. We characterize and, where possible, prove essential properties of neural algorithms: expressivity, learning, and robustness. We show how observed emergent behavior can arise from network dynamics, and we develop algorithms for learning more about the network structure of the brain.

Seth Shelley-Abrahamson

Title: On Representations of Rational Cherednik Algebras
Date: Thursday, April 19, 2018 | 11:00am | Room: 2-255
Committee: Pavel Etingof (advisor and thesis committee chair), George Lusztig, David Vogan

Abstract

This thesis introduces and studies two constructions related to the representation theory of rational Cherednik algebras: the refined filtration by supports for the category O and the Dunkl weight function.

The refined filtration by supports provides an analogue for rational Cherednik algebras of the Harish-Chandra series appearing in the representation theory of finite groups of Lie type. In particular, irreducible representations in the rational Cherednik category O with particular generalized support conditions correspond to irreducible representations of associated generalized Hecke algebras. An explicit presentation for these generalized Hecke algebras is given in the Coxeter case, classifying the irreducible finite-dimensional representations in many new cases.

The Dunkl weight function K is a holomorphic family of tempered distributions on the real reflection representation of a finite Coxeter group W with values in linear endomorphisms of an irreducible representation of W. The distribution K gives rise to an integral formula for the Gaussian inner product on a Verma module in the rational Cherednik category O. At real parameter values, the restriction of K to the regular locus in the real reflection representation can be interpreted as an analytic function taking values in Hermitian forms, invariant under the braid group, on the image of a Verma module under the Knizhnik-Zamolodchikov (KZ) functor. This provides a bridge between the study of invariant Hermitian forms on representations of rational Cherednik algebras and of Hecke algebras, allowing for a proof that the KZ functor preserves signatures in an appropriate sense.

Jonasz Slomka

Title: Generalized Navier—Stokes equations for active turbulence.
Date: Tuesday, April 24, 2018 | 10:00am | Room: 2-449
Committee: Jorn Dunkel, John Bush, Alex Townsend

Abstract

Recent experiments show that active fluids stirred by swimming bacteria or ATP-powered microtubule networks can exhibit complex flow dynamics and emergent pattern scale selection. Here, I will discuss a simplified phenomenological approach to 'active turbulence', a chaotic non-equilibrium steady-state in which the solvent flow develops a dominant vortex size. This approach generalizes the incompressible Navier Stokes equation by accounting for active stresses through a linear instability mechanism, in contrast to externally driven classical turbulence. This minimal model can reproduce experimentally observed velocity statistics and is analytically tractable in planar and curved geometry. Exact stationary bulk solutions include Abrikosov-type vortex lattices in 2D and chiral Beltrami fields in 3D. Numerical simulations for a plane Couette shear geometry predict a low viscosity phase mediated by stress defects, in qualitative agreement with recent experiments on bacterial suspensions. Considering active analog of Stokes’ second problem, our numerical analysis predicts that a periodically rotating ring will oscillate at a higher frequency in an active fluid than in a passive fluid, due to an activity-induced reduction of the fluid inertia. The model readily generalizes to curved geometries. On a two-sphere, we present exact stationary solutions and predict a new type of upward energy transfer mechanism realized through the formation of vortex chains, rather than the merging of vortices, as expected from classical 2D turbulence. In 3D simulations on periodic domains, we observe spontaneous mirror-symmetry breaking realized through Beltrami-like flows, which give rise to upward energy transfer, in contrast to the classical direct Richardson cascade. Our analysis of triadic interactions supports this numerical prediction by establishing an analogy with a forced rigid body dynamics and reveals a previously unknown triad invariant for classical turbulence.

Lucas Tambasco

Title: Walking droplets confined by applied or topographically-induced potentials: dynamics and stability
Date: Friday, April 27, 2018 | 2:00pm | Room: 4-237
Committee: John W. M. Bush, Rodolfo R. Rosales, and Anand U. Oza (New Jersey Institute of Technology, NJ)

Abstract

In 2005, Yves Couder and coworkers discovered that a millimetric droplet of silicone oil may walk on the surface of a vertically-vibrating fluid bath, displaying features that were once thought to be peculiar to quantum mechanics. We here explore this hydrodynamic pilot-wave system in an integrated theoretical and experimental approach. We provide a theoretical characterization of the transition to chaos in orbital pilot-wave dynamics for droplets walking in the presence of a Coulomb, Coriolis, or central harmonic force. We proceed by investigating this hydrodynamic system above the Faraday threshold experimentally, with an aim of finding mechanisms to trap drops. Specifically, we report a hydrodynamic analog to the Talbot effect, namely the Faraday-Talbot effect, and show that drops may become trapped at the extrema of the resulting Faraday-Talbot wavefield. We also characterize the dynamics of droplets bouncing and walking above the Faraday threshold, indicating regimes of particle trapping. We investigate the effect of bath topography in drop dynamics by considering a circular well that induces a circularly-symmetric Faraday wave pattern. In this regime, we show that droplets become trapped into stable circular orbits. Finally, with a view to extend the phenomenological range of this hydrodynamic system, we consider a generalized pilot-wave framework, in which the relative magnitudes of dynamical parameters are altered relative to those obtained in the fluid system. In this generalized framework, we validate the theoretical result by Durey et al. relating the particle's mean wavefield to the emerging statistics.

Konstantin Tolmachov

Title: Towards a functor between affine and finite Hecke categories in type A
Date: Friday, April 27, 2018 | 4:00pm | Room: 2-136
Committee: Roman Bezrukavnikov (chair), Pavel Etingof, George Lusztig

Abstract

In this thesis we construct a functor from a perfect subcategory of a coherent version of an affine Hecke category in type A to a finite constructible Hecke category, partly categorifying a certain natural homomorphism of the corresponding Hecke algebras. This homomorphism sends generators of the Bernstein's commutative subalgebra inside the affine Hecke algebra to Jucys-Murphy elements in the finite Hecke algebra. Construction employs a general strategy devised by Bezrukavnikov to prove an equivalence of coherent and constructible variants of the affine Hecke category. Namely, we identify an action of the category Rep(GL(n))\$ on the finite Hecke category, and lift this action to a functor from a perfect derived category of a Steinberg variety, by equipping it with various additional data.

Francisco Unda

Title: Combinatorial Incremental Problems
Date: Wednesday, August 8, 2018 | 11:00am | Room: 2-361
Committee: Michel Goemans, Jon Kelner and Ankur Moitra

Abstract

We introduce the class of Incremental combinatorial problems, where solutions are evaluated as they are being built, instead of only measuring performance at the last step.Even though many of these problems have been studied, it has usually been in isolation, so a first objective of this document is to present them under the same framework. We present the incremental analog of several classical combinatorial problems, and present efficient algorithms to find approximate solutions to these problems, improving on almost all known approximation constants. We try to concentrate on the difficulty brought on by their incremental nature, and show some properties of solutions for broad subclasses of problems, usually carrying results and algorithms from the non incremental version of the problem, that we use as subroutines. The first section introduces incremental problems formally, and surveys results for specific examples. In the second section we present improved algorithms for these incremental problems. We present an improved constant of approximation for minimization problems and in particular for the incremental shortest paths problem. For maximization problems, we give an algorithm that improves upon the best constant of approximation for the incremental maximum weight matching problem. We also study the performance of two heuristics in the case of cardinality maximization, Quickest-to-Ultimate (Q2U), and Quickest-Increment (QI). We also describe a useful integrality property for the approximation of solutions in this case, and show that it is satisfied in many cases, including the incremental maximum matching problem.

Umut Varolgunes

Title: Mayer-Vietoris sequence for relative symplectic cohomology
Date: Friday, April 6, 2018 | 10:00am | Room: 2-361
Committee: Paul Seidel (advisor), Larry Guth, David Treumann (Boston College)

Abstract

In this thesis, I construct and investigate the properties of a Floer theoretic invariant called relative symplectic cohomology. The construction is based on Hamiltonian Floer theory. It assigns a module over the Novikov ring to every compact subset of any closed symplectic manifold. I show the existence of restriction maps, and prove that they satisfy the Hamiltonian isotopy invariance property, discuss a Kunneth formula, and do some example computations. Relative symplectic homology is then used to establish a general criterion for displaceability of subsets. Finally, moving on to the main contribution of my thesis, I identify a natural geometric situation in which relative symplectic homology of two subsets satisfy the Mayer-Vietoris property. This is tailored to work under certain integrability assumptions, the weakest of which introduces a new geometric object called a barrier - roughly, a one parameter family of rank 2 coisotropic submanifolds. The proof uses a deformation argument in which the topological energy zero (i.e. constant) Floer solutions are the main actors.

Alex Wein

Title: Statistical Estimation in the Presence of Group Actions
Date: Thursday, April 19, 2018 | 2:00pm | Room: 2-449
Committee: Ankur Moitra (advisor), Michel Goemans, Philippe Rigollet

Abstract

Imagine we want to recover an unknown vector given many noisy copies of it, except each copy is cyclically shifted by an unknown offset (this is "multi-reference alignment"). Or imagine we want to reconstruct an unknown 3D structure (e.g. a molecule) given many noisy pictures of it taken from different unknown angles (this is "cryo-EM"). These problems (and many others) involve the action of unknown group elements drawn randomly from a compact group such as the cyclic group Z/p or the rotation group SO(3).

In this thesis we study two statistical models for estimation in the presence of group actions. The first is the "synchronization" model in which we attempt to learn an unknown collection of group elements based on noisy pairwise comparisons. The second is the "orbit recovery" model in which we observe noisy copies of a hidden signal, each of which is acted upon by a random group element. For both of these models, we explore the fundamental statistical limits as well as the fundamental computational limits (i.e. how well can an efficient algorithm do?). We use methods from a wide variety of areas, including statistical physics, approximate message passing, representation theory, contiguity and the associated second moment method, invariant theory, and algebraic geometry.