Graduate Thesis Defenses 2017

Mohammad Bavarian

Title: Parallel Repetition of Multi-party and Quantum Games via Anchoring and Fortification
Date: Thursday May 4th, 2017 | 4:00pm | Room: 32-G449 (Kiva)
Committee: Madhu Sudan (Advisor, Harvard), Peter W. Shor (Chair), Ankur Moitra, Elchanan Mossel

Abstract

Parallel repetition is a natural operation for amplifying the hardness inherent in multiplayer games. Despite being very simple to define, it has been known since the 90's that the behavior of this operation is subtle. For example, even though an exponential decay of the value of games under parallel repetition can be suspected from the definition, the exact nature of behavior as understood by the relevant counter-examples reveal various intriguing properties and surprises.

Through the work of many theoretical computer scientists over two decades (e.g.~Feige, Kilian, Raz, Holenstein, Rao, etc.) the behavior of parallel repetition of two-player classical games came to be well-understood. But until very recently, no similar hardness amplification results were known for multiplayer (in games with more than two players) and quantum games. This thesis focuses on these two problems and resolves some of the most important challenges regarding the parallel repetition of multiplayer and quantum games. Drawing from the works of Feige-Kilian and Moshkovitz, we introduce operations of anchoring and fortification which are central to our approach to obtaining exponential hardness amplification in our general setting. We show how these simple operations enable us to circumvent some of the major difficulties in obtaining strong parallel repetition results for games with three (or more) players and quantum games.

Florent Bekerman

Title: Transport methods and universality for $\beta$-ensembles.
Date: Tuesday, October 31, 2017 | 3:00pm | Room: 2-449
Committee: Alice Guionnet (advisor), Alexei Borodin, Vadim Gorin

Abstract

In this thesis, we investigate the local and global properties of the eigenvalues of $\beta$-ensembles. A lot of attention has been drawn recently on the universal properties of $\beta$-ensembles, and how their local statistics relate to those of Gaussian ensembles. We use transport methods to prove universality of the eigenvalue gaps in the bulk and at the edge, in the single cut and multicut regimes. In a different direction, we also prove Central Limit Theorems for the linear statistics of $\beta$-ensembles at the macroscopic and mesoscopic scales.

Sylvain Carpentier

Title: Rational Matrix differential Operators and Integrable Systems of PDEs
Date: Friday, April 28, 2017 | 3:00pm | Room: 2-361
Committee: Victor Kac, Pavel Etingof, Alberto DeSole

Abstract

A key feature of integrability for systems of evolution PDEs $u_t=F(u)$, where $F$ lies in a differential algebra of functionals $\mathcal V$ and $u=(u_1,...,u_{\ell})$ depends on one space variable $x$ and time $t$, is to be part of an infinite hierarchy of generalized symmetries. Recall that $\mathcal V$ carries a Lie algebra bracket $\{F,G\}=X_F(G)-X_G(F)$, where $X_F$ denotes the evolutionnary vector field attached to $F$. In all known examples, these hierarchies are constructed by means of Lenard-Magri sequences: one can find a pair of matrix differential operators $(A(\partial),B(\partial))$ and a sequence $(G_n)_{n \geq 0} \in \mathcal V^{\ell}$ such that

• $F=B(G_N)$ for some $N \geq 0$,
• $\{B(G_n),B(G_m)\}=0$ for all $n,m \geq 0$,
• $B(G_{n+1})=A(G_n)$ for all $n \geq 0$.

We show that in the scalar case $\ell=1$ a necessary condition for a pair of differential operators $(A,B)$ to generate a Lenard-Magri sequence is that for all constants $\lambda$, the family $C_{\lambda}=A+ \lambda B$ must satisfy for all $F,G \in \mathcal V$

{$C_{\lambda}(F),C_{\lambda}(G)$} $\in Im C_{\lambda}$.

We call such pairs integrable. We give a sufficient condition on an integrable pair of matrix differential operators $(A,B)$ to generate an infinite Lenard-Magri sequence when the rational matrix differential operator $L=AB^{-1}$ is weakly non-local and the algebra of differential functions $\mathcal V$ is either $\mathbb{Z}$ or $\mathbb{Z}/2\mathbb{Z}$-graded. This is applied to many systems of evolution PDEs to prove their integrability.

Chenjie Fan

Title: On long time dynamic and singularity formation of NLS
Date: Thursday, April 27, 2017 | 2:30pm | Room: 2-147
Committee: Gigliola Staffilani (Advisor& Chair), Larry Guth, David Jerison

Abstract

In this thesis, we investigate the long time behavior of focusing mass critical nonlinear Schrödinger equation (NLS). We will focus on the singularity formation and long time asymptotics. To be speci c, there are two parts in the thesis. In the rst part, we give a construction of log-log blow up solutions which blow up at 𝑚 prescribed points simultaneously. In the second part, we show weak convergence to ground state for certain radial blow up solutions to NLS at well chosen time sequence.

Miriam Farber

Title: Arrangement of minors in the positive Grassmannian
Date: Monday, April 24, 2017 | 11:30am | Room: 2-361
Committee: Alex Postnikov, Richard Stanley and Tom Roby

Abstract

This thesis consists of three parts. In the first chapter we discuss arrangements of equal minors of totally positive matrices. More precisely, we investigate the structure of equalities and inequalities between the minors. We show that arrangements of equal minors of largest value are in bijection with sorted sets, which earlier appeared in the context of alcoved polytopes and Gröbner bases. Maximal arrangements of this form correspond to simplices of the alcoved triangulation of the hypersimplex; and the number of such arrangements equals the Eulerian number. On the other hand, we prove in many cases that arrangements of equal minors of smallest value are weakly separated sets. Weakly separated sets, originally introduced by Leclerc and Zelevinsky, are closely related to the positive Grassmannian and the associated cluster algebra. However, we also construct examples of arrangements of smallest minors which are not weakly separated using chain reactions of mutations of plabic graphs.

In the second chapter, we investigate arrangements of t-th largest minors and their relations with alcoved triangulation of the hypersimplex. We show that second largest minors correspond to the facets of the simplices. We then introduce the notion of cubical distance on the dual graph of the triangulation, and study its relations with these arrangements. In addition, we show that arrangements of largest minors induce a structure of a partially ordered set on the entire collection of minors. We use this triangulation of the hypersimplex to describe a 2-dimensional grid structure on this poset.

In the third chapter, we obtain new families of quadratic Schur function identities, via examination of several types of networks and the usage of Lindström-Gessel- Viennot lemma. We generalize identities obtained by Kirillov, Fulmek and Kleber and also prove a conjecture suggested by Darij Grinberg.

Hilary Finucane

Title: Functional and cross-trait genetic architecture of common diseases and complex traits
Date: Friday, April 28, 2017 | 1:30pm | Room: 2-147
Committee: Alkes Price, Bonnie Berger, Ankur Moitra, Jon Kelner

Abstract

In this thesis, I introduce new methods for learning about diseases and traits from genetic data. First, I introduce a method for partitioning heritability by functional annotation from genome-wide association summary statistics, and I apply it to 17 diseases and traits and many different functional annotations. Next, I show how to apply this method to use gene expression data to identify disease- relevant tissues and cell types. I next introduce a method for estimating genetic correlation from genome-wide association summary statistics and apply it to estimate genetic correlations between all pairs of 24 diseases and traits. Finally, I consider a model of disease subtypes and I show how to determine a lower bound on the sample size required to distinguish between two disease subtypes as a function of several parameters.

Nate Harman

Title: Deligne categories and representation stability in positive characteristic
Date: Tuesday, May 2, 2017 | 4:00pm | Room: 2-361
Committee: Pavel Etingof, Roman Bezrukavnikov, Andrei Negut

Abstract

We study the asymptotic behavior of the representation theory of symmetric groups S_n in positive characteristic as n grows to infinity with the goal of understanding and generalizing the Deligne categories Rep(S_t) as well as the theory of FI-modules and representation stability to the positive characteristic setting. We also give q-analogs of some of our results in the context of unipotent representations of finite general linear groups in non-defining characteristic.

Alisa Knizel

Title: Random domino tilings: gap probabilities, local and global asymptotics.
Date: Monday, April 3, 2017 | 3:15pm | Room: 2-449
Committee: Alexei Borodin, Alexander Postnikov, Mark Adler

Abstract

In the thesis we explore and develop two different approaches to the study of random tiling models.

First, we consider tilings of a hexagon by rhombi, viewed as 3D random stepped surfaces with a measure proportional to $q^{−Volume}$. Such model is closely related to q-Hahn orthogonal polynomial ensembles, and we use this connection to obtain results about the local behavior of the model. In terms of the q-Hahn orthogonal polynomial ensemble, our goal is to show that the one-interval gap probability function can be expressed through a solution of the asymmetric q-Painlevé V equation. The case of the q-Hahn ensemble we consider, is the most general case of the orthogonal polynomial ensembles that have been studied in this context. Our approach is based on the analysis of q-connections on $\mathbb{P}^1$ with a particular singularity structure. It requires a new derivation of a q-difference equation of Sakai’s hierarchy of type $A_2^{(1)}$ . We also calculate its Lax pair. Following Arinkin and Borodin, we introduce the notion of the $\tau$-function of a q-connection and its isomonodromy transformations. We show that the gap probability function of the q-Hahn ensemble can be viewed as the $\tau$-function for an associated q-connection and its isomonodromy transformations.

Secondly, in collaboration with Alexey Bufetov we consider asymptotics of a domino tiling model on a class of domains which we call rectangular Aztec diamonds. We prove the Law of Large Numbers for the corresponding height functions and provide explicit formulas for the limit. For a special class of examples an explicit parametrization of the frozen boundary, which turns out to be an algebraic curve, is given. The main result is the convergence of the fluctuations of the height functions to the Gaussian Free Field in appropriate coordinates. Our approach is based on a recently developed moment method for discrete particle systems.

Xue "Gaku" Liu

Title: The topology of Baues complexes and flip graphs
Date: Wednesday, April 19, 2017 | 10:00am | Room: 2-147
Committee: Alexander Postnikov (advisor), Richard Stanley, Olivier Bernardi

Abstract

This thesis contains several results on the connectedness of Baues complexes and flip graphs, which are topological spaces modeling certain sets coming from geometric combinatorics. These sets include the triangulations of a polytope, the tilings of a zonotope, and the extensions of an oriented matroid. A classical example of such a space is the associahedron, which models the triangulations of a polygon. Some long-standing conjectures are resolved, including the connectedness of triangulations of a product of two simplices and the sphericity of extension spaces of realizable oriented matroids.

Asad Lodhia

Title: Topics in Linear Spectral Statistics of Random Matrices
Date: Tuesday, April 25th | 2:00pm | Room: 2-449
Committee: Alice Guionnet (advisor), Philippe Rigollet and Alexei Borodin

Abstract

The local and global behaviour of the eigenvalues of a random matrix is a topic of great interest in probability theory. In recent years there has been a great deal of progress in the study of the local behaviour of the eigenvalues of a random Wigner matrix along with similar results in the study of $\beta$-ensembles. In this thesis, we discuss our contributions to the study of fluctuations of linear statistics of eigenvalues at a local scale for Wigner and $\beta$-ensembles using the recent work on local laws. Along a different direction, we discuss our contribution to understanding the global behaviour of eigenvalues of a matrix arising in statistics, called Kendall's Rank Correlation matrix.

Laszlo Miklos Lovasz

Title: Regularity and removal lemmas and their applications
Date: Wednesday, May 3, 2017 | 1:00pm | Room: 2-449
Committee: Jacob Fox (advisor), Henry Cohn (chair), and Michel Goemans

Abstract

In this thesis, we analyze the regularity method pioneered by Szemer\'edi, and also discuss one of its prevalent applications, the removal lemma.

First, we prove a new lower bound on the number of parts required in a version of Szemer\'edi's regularity lemma, determining the order of the tower height in that version up to a constant factor. This addresses a question of Gowers.

Next, we turn to algorithms. We give a fast algorithmic Frieze-Kannan (weak) regularity lemma that improves on previous running times. We use this to give a substantially faster deterministic approximation algorithm for counting subgraphs. Previously, only an exponential dependence of the running time on the error parameter was known; we improve it to a polynomial dependence. We also revisit the problem of finding an algorithmic regularity lemma, giving approximation algorithms for some co-NP-complete problems. We show how to use the Frieze-Kannan regularity lemma to approximate the regularity of a pair of vertex sets. We also show how to quickly find, for each $\epsilon'>\epsilon$, an $\epsilon'$-regular partition with $k$ parts if there exists an $\epsilon$-regular partition with $k$ parts.

After studying algorithms, we turn to the arithmetic setting. Green proved an arithmetic regularity lemma, and used it to prove an arithmetic removal lemma. The bounds obtained, however, were tower-type, and Green posed the problem of improving the quantitative bounds on the arithmetic triangle removal lemma, and, in particular, asked whether a polynomial bound holds. The previous best known bound was tower-type with a logarithmic tower height. We solve Green's problem, proving an essentially tight bound for Green's arithmetic triangle removal lemma in $\mathbb{F}_p^n$.

Finally, we give a new proof of a regularity lemma for permutations, improving the previous tower-type bound on the number of parts to an exponential bound.

Denis Nardin

Title: Stability and distributivity over an orbital ∞-category
Date: Monday, April 10, 2017 | 4:30pm | Room: 2-131
Committee: C. Barwick (advisor), H. Miller and G. Tabuada

Abstract

The category of G-spectra plays an important role in homotopy theory, even when a group action is not obviously involved. In this talk we will present a universal property for it providing an alternate proof of the Guillou-May theorem. If time permits, we will use it to provide a uniqueness theorem for the norm functors.

David B. Rush

Title: Computing the Lusztig--Vogan Bijection
Date: Wednesday, July 5, 2017 | 4:00pm | Room: 2-361
Committee: Roman Bezrukavnikov, George Lusztig, David A. Vogan Jr. (Advisor & Chair)

Abstract

Let $G$ be a connected complex reductive algebraic group with Lie algebra $\mathfrak{g}$. The Lusztig--Vogan bijection relates two bases for the bounded derived category of $G$-equivariant coherent sheaves on the nilpotent cone $\mathcal{N}$ of $\mathfrak{g}$. One basis is indexed by $\Lambda^+$, the set of dominant weights of $G$, and the other by $\Omega$, the set of pairs $(\mathcal{O}, \mathcal{E})$ consisting of a nilpotent orbit $\mathcal{O} \subset \mathcal{N}$ and an irreducible $G$-equivariant vector bundle $\mathcal{E} \rightarrow \mathcal{O}$. The existence of the Lusztig--Vogan bijection $\gamma \colon \Omega \rightarrow \Lambda^+$ was proven by Bezrukavnikov, and an algorithm computing $\gamma$ in type $A$ was given by Achar. Herein we present a combinatorial description of $\gamma$ in type $A$ that subsumes and dramatically simplifies Achar's algorithm.

Jay Shah

Title: Parametrized higher category theory
Date: Monday, May 1, 2017 | 4:30pm | Room: 2-131
Committee: C. Barwick (chair), H. Miller, G. Tabuada

Abstract

In this thesis, we develop some foundations for the category theory of ∞-categories fibered over a base ∞-category. Our main contribution is a theory of parametrized homotopy limits and colimits, which recovers and extends the Dotto-Moi theory of G-colimits when the base is taken to be the orbit category of a finite group. We use this theory to state and prove a universal property for the G-∞-category of G-spaces, as a G-∞-category, affirming a conjecture of Mike Hill.

Xin Sun

Title: Matings of negatively correlated trees with applications to Schnyder woods and bipolar orientations
Date: Wednesday, April 26, 2017 | 10:30am | Room: 2-449
Committee: Scott Sheffield (chair, thesis adviser), Alexei Borodin, Stephane Benoist

Abstract

In this thesis, we study the mating of tree approach to Liouville quantum gravity decorated with SLE curves and its application to the scaling limit theory of decorated random planar maps. We focus on the less investigated regime where the SLE parameter $\kappa$ is larger than $8$. We obtain three main results. First, we identify the covariance of the Brownian motion in the Mating of Tree Theorem for $\kappa>8$, answering a question of Duplantier-Miller-Sheffield. Second, we prove the joint convergence of bipolar oriented triangulations and their dual in the peanosphere topology, confirming a conjecture of Kenyon-Miller-Sheffield-Wilson. Third, we prove the joint convergence of the three trees and their dual in a uniformly sampled Schnyder wood in the peanosphere topology. The third result also yields a description of the continuum limit of a widely used planar embedding due to Schnyder. The scaling limits in the second and the third result involve Peano curves coupled in the same imaginary geometry with different angles. In order to establish the scaling limits, we extend the mating of tree theory to multiple Peano curves in the same imaginary geometry.

Daniel C Thompson

Title: Representation theory of the global Cherednik algebra
Date: Tuesday, April 18, 2017 | 11:00am | Room: 2-361
Committee: Pavel Etingof (chair), Roman Bezrukavnikov, Ivan Losev (Northeastern)

Abstract

This thesis studies the representation theory of Cherednik algebras associated to a complex algebraic varieties which carries the action of a finite group.

First, we prove that the Knizhnik-Zamolodchikov functor from the category of $\mathscr{O}$-coherent modules for the Cherednik algebra to finite dimensional modules over the Hecke algebra is essentially surjective. Then we begin to use this result to study the analog of the GGOR category $\mathcal{O}$ for Cherednik algebras on Riemann surfaces and on products of elliptic curves. In particular we give conditions on the parameters under which this category $\mathcal{O}$ analog is nonzero.

Our next goal is to generalize several basic results from the theory of $\mathscr{D}$-modules to the representation theory of rational Cherednik algebras. We relate characterizations of holonomic modules in terms of singular support and Gelfand-Kirillov dimension. We study pullback, pushforward, and dual on the derived category of (holonomic) Cherednik modules for certain classes of maps between varieties. We prove, in the case of generic parameters for the rational Cherednik algebra, that pushforward with respect to an open affine inclusion preserves holonomicity.

Finally, we relate the global sections algebra of the sheaf of Cherednik algebras associated to a smooth quadric hypersurface of $\mathbb{P}^n$ to the Dunkl angular momentum algebra of Feigin-Hakobyan. In particular, this lets us relate the angular momentum algebra for a rank 3 Coxeter group to the rank 2 symplectic reflection algebra for a corresponding finite subgroup of $SL_2$.

Adrian Vladu

Title: Shortest Paths, Markov Chains, Matrix Scaling and Beyond: Improved Algorithms Through the Lens of Continuous Optimization
Date: Thursday, May 11, 2017 | 3:00pm | Room: 32G-575
Committee: Jonathan Kelner (thesis supervisor), Aleksander Madry (thesis supervisor), Ankur Moitra

Abstract

In this thesis, we build connections between classic methods from convex optimization and the modern toolkit from the fast Laplacian solver literature, in order to make progress on a number of fundamental algorithmic problems:

• We develop a faster algorithm for the unit capacity minimum cost flow problem, which encompasses the shortest path with negative weights and minimum cost bipartite perfect matching problems. In the case of sparse graphs, this provides the first running time improvement for these problems in over 25 years.
• We initiate the study of solving linear systems involving directed Laplacian matrices, and devise an almost-linear time algorithm for this task. This primitive enables us to also obtain almost-linear time algorithms for computing an entire host of quantities associated with Markov chains, such as stationary distributions, personalized PageRank vectors, hitting times, or escape probabilities. This significantly improves over the previous state-of-the-art, which was based on simulating random walks, or applying fast matrix multiplication.
• We develop faster algorithms for scaling and balancing nonnegative matrices, two fundamental problems in scientific computing, significantly improving over the previously known best running times. In particular, if the optimal scalings/balancings have polynomially bounded condition numbers, our algorithms run in nearly-linear time.

Beyond that, we leverage and extend tools from convex geometry in order to design an algorithm for online pricing with nearly-optimal regret. We also use convex optimization to shed a new light on the approximate Carathéodory problem, for which we give a deterministic nearly-linear time algorithm, as well as matching lower bounds.

Menglu Wang

Title: Gaussian free field, Schramm-Loewner evolution and Liouville quantum gravity
Date: Thursday, April 27, 2017 | 2:00pm | Room: 2-429
Committee: Scott Sheffield (advisor), Alexei Borodin, Stephane Benoist

Abstract

Consider an instance $h$ of the Gaussian free field on a simply connected domain. Let $\lambda=\pi/2$. It has been proved that if $h$ has boundary value $-\lambda$ on one boundary arc, and $\lambda$ on the other, then it has a well-defined level line connecting the endpoints of the arcs, whose law is SLE$_4$. In the first part of the thesis, we make a generalization that when $h$ has piecewise constant boundary conditions, it has a level line connecting two boundary points and the law is SLE$_4{\underline{(\rho)}}$, which are variants of SLE$_4$. We study several properties of the level lines: the monotonicity behavior, time-reversal and target-independence. Since CLE$_4$ is a random collection of SLE$_4$-type loops, we are able to construct a coupling between CLE$_4$ with time parameter and GFF using a sequence of level loops. This is a joint work with Hao Wu.

In the second part, we study Liouville quantum gravity. In Liouville quantum gravity, one seeks to define a measure $\mu^h = e^{\gamma h(z)} dz$ where $h$ is an instance of the Gaussian free field on a planar domain $D$. Since $h$ is a distribution, not a function, one needs a regularization procedure to make this precise: for example, one may let $h_\epsilon(z)$ be the average value of $h$ on the circle of radius $\epsilon$ centered at $z$ and then write $\mu^h = \lim_{\epsilon \to 0} \epsilon^{\frac{\gamma^2}{2}} e^{\gamma h_\epsilon(z)} dz$. If $\phi: \tilde D \to D$ is a conformal map, one can write $\tilde h = h \circ \phi + Q \log |\phi'|$, where $Q = 2/\gamma + \gamma/2$. The measure $\mu^{\tilde h}$ on $\tilde D$ is then a.s. equivalent to the pullback via $\phi^{-1}$ of the measure $\mu^h$ on $D$. Interestingly, although the coordinate change rule a.s. holds for each given $\phi$, nobody has ever proved that it a.s. holds simultaneously for all possible $\phi$. We will prove that this is indeed the case. This is a joint work with Scott Sheffield.

Ben Yang

Title: Polynomial Partitioning and Incidence Problems in Higher Dimensions.
Date: Wednesday, April 26, 2017 | 1:30pm | 2-361
Committee: Larry Guth (advisor & chair), Pavel Etingof, Ankur Moitra

Abstract

Incidence geometry is the study of the intersection patterns of simple geometric objects. One of the breakthroughs in this field is the polynomial partitioning technique introduced by Guth and Katz. I will present two results on incidence problems with high-dimensional objects: an almost tight bound on the number of joints formed by varieties in R^n and a tight bound on the number of flags in R^n. The proofs are based on the polynomial partitioning technique and its variations.

Yun William Yu

Title: Compressive algorithms for search and storage in biological data
Date: Monday, April 24, 2017 | 10:00am | Room: 32-G575
Committee: Bonnie Berger (advisor), Peter Shor, Jörn Dunkel

Abstract

Many biological datasets exhibit a well-defined structure that can be exploited to design efficient algorithms. In this work, we introduce a framework for similarity search based on characterizing a dataset’s entropy and fractal dimension. We prove that searching scales in time with metric entropy (number of covering hyperspheres), if the fractal dimension of the dataset is low, and scales in space with the sum of metric entropy and information-theoretic entropy (randomness of the data). Using these ideas, we present accelerated versions of standard bioinformatics search tools. These include tools in the application domains of small-molecule similarity, metagenomics, protein structure search, and sequence alignment.

Additionally, we also present work on filtering empirical base-calling quality scores from Next Generation Sequencing data. By using the sparsity of k-mers of sufficient length in the human genome and imposing a human prior through the use of frequent k-mers in a large corpus of human DNA reads, we are able to quickly discard over 90% of the information found in those quality scores while retaining or even improving downstream variant-calling accuracy. This filtering step allows for fast lossy compression of quality scores.