# Graduate Thesis Defenses 2009

## Summer 2009

### Oaz Nir

High-throughput Single-cell Morphological Data: Signaling Pathway Inference, Genetic Contributions to Variability, and Integration with Transcriptional Data
Friday August 21, 2009
12:30pm, Room 32-G575
Committee: Bonnie Berger (thesis advisor), Daniel Kleitman, Dr.Norbert Perrimon (Harvard Medical School and HHMI)

#### Abstract

Metastasis, the migration of cancer cells from the primary site of tumorigenesis and the subsequent invasion of secondary tissues, causes the vast majority of cancer deaths. To spread, metastatic cells dramatically rearrange their shape in complex, dynamic fashions. Genes encoding signaling proteins that regulate cell shape in normal cells are often mutated in cancer, especially in highly metastatic disease. To study these key signaling proteins in locomotion and metastasis, we develop and validate statistical methods to extract information from high-throughput morphological data from genetic screens.

Our contributions fall into three major categories. 1) To define and apply robust statistical measures to identify genes regulating morphological variability. We develop and thoroughly test methods for measuring morphological variability of single-cells populations, and apply these metrics to genetic screens in yeast and fly. We further apply these techniques to subsets of genes involved in cellular processes to study genetic contributions to variability in these processes. We propose new roles for genes as suppressors or enhancers of morphological noise. We validate our findings on the basis of known gene function and network architecture. 2) To perform inference of protein signaling relationships by utilizing high-throughput morphological data. We apply machine-learning techniques to systematically identify genetic interactions between proteins on the basis of image-based data from double-knockout screens. Next, we focus on RhoGTPases and RhoGTPase Activating Proteins (RhoGAPs) in Drosophila., where by using basic knowledge of network architecture we apply our techniques to detect signaling relationships.

3) To integrate expression data with high-throughput morphological data to study the mechanisms for determination of cell morphology. We utilize morphological and microarray data from fly screens. By comparing expression data between control treatment conditions and treatment conditions displaying morphological phenotypes (e.g. high population variability), we identify genes and pathways correlated with this class distinction, thereby validating our previous studies and providing further insight into the determination of morphology.

A key challenge in systems biology is to analyze emerging high-throughput image-based data to understand how cellular phenotypes are genetically encoded. Our work makes significant contributions to the literature on high-throughput morphological study and describes a path for future investigation.

### Michael Baym

Large, Noisy, and Incomplete: Mathematics for Modern Biology
Monday August 3, 2009
12:30pm, Room 32-G575
Committee: Bonnie Berger (thesis advisor), Jonathan Kelner, Leonid Mirny (MIT Biophysics)

#### Abstract

In recent years there has been a great deal of new activity at the interface of biology and computation. This has largely been driven by the massive influx of data from new experimental technologies, particularly high-throughput sequencing and array-based data. These new data sources require both computational power and new mathematics to properly piece them apart. This thesis discusses two problems in this field, network reconstruction and multiple network alignment, and draws the beginnings of a connection between information theory and population genetics.

The first section addresses cellular signaling network inference. A central challenge in systems biology is the reconstruction of biological networks from high-throughput data sets, We introduce a new method based on parameterized modeling to infer signaling networks from perturbation data. We use this on Microarray data from RNAi knockout experiments to reconstruct the Rho signaling network in Drosophila.

The second section addresses information theory and population genetics. While much has been proven about population genetics, a connection with information theory has never been drawn. We show that genetic drift is naturally measured in terms of the entropy of the allele distribution. We further sketch a structural connection between the two fields.

The final section addresses multiple network alignment. With the increasing availability of large protein-protein interaction networks, the question of protein network alignment is becoming central to systems biology. We introduce a new algorithm, IsoRankN to compute a global alignment of multiple protein networks. We test this on the five known eukaryotic protein-protein interaction (PPI) networks and show that it outperforms existing techniques.

### Damian Burch

Intercalation Dynamics in Lithium-Ion Batteries
Wednesday July 29, 2009
2:00pm, Room 2-135
Committee: Martin Bazant (thesis advisor), Steven Johnson, John Bush

#### Abstract

A new continuum model has been proposed by Singh, Ceder, and Bazant for the ion intercalation dynamics in a single crystal of rechargeable-battery electrode materials. It is based on the Cahn-Hilliard equation coupled to reaction rate laws as boundary conditions to handle the transfer of ions between the crystal and the electrolyte. In this thesis, I carefully derive a second set of boundary conditions necessary to close the original PDE system via a variational analysis of the free energy functional; I include a thermodynamically-consistent treatment of the reaction rates; I develop a semi-discrete finite volume method for numerical simulations; and I include a careful asymptotic treatment of the dynamical regimes found in different limits of the governing equations. Further, I will present several new findings relevant to batteries:

Defect Interactions: When applied to strongly phase-separating, highly anisotropic materials such as LiFePO4, this model predicts phase-transformation waves between the lithiated and unlithiated portions of a crystal. This work extends the analysis of the wave dynamics, and describes a new mechanism for current capacity fade through the interactions of these waves with defects in the particle.

Size-Dependent Spinodal and Miscibility Gaps: This work demonstrates that the model is powerful enough to predict that the spinodal and miscibility gaps shrink as the particle size decreases. It is also shown that boundary reactions are another general mechanism for the suppression of phase separation.

Multi-Particle Interactions: This work presents the results of parallel simulations of several nearby crystals linked together via common parameters in the boundary conditions. The results demonstrate the so-called mosaic effect: the particles tend to fill one at a time, so much so that the particle being filled actually draws lithium out of the other ones. Moreover, it is shown that the smaller particles tend to phase separate first, a phenomenon seen in experiments but difficult to explain with any other theoretical model.

### Kevin Matulef

Testing and Learning Boolean Functions
Friday July 17, 2009
2:00pm, Room 32-G575
Committee: Ronitt Rubinfeld (EECS, thesis advisor), Michael Sipser, Jon Kelner

#### Abstract

Given a function $f$ on $n$ inputs, we consider the problem of testing whether $f$ belongs to a concept class $C$, or is far from every member of $C$. An algorithm that achieves this goal for a particular $C$ is called a property testing algorithm, and can be viewed as relaxation of a proper learning algorithm, which must also return an approximation to $f$ if it is in $C$. We give property testing algorithms for many dirent classes $C$, with a focus on those that are fundamental to machine learning, such as halfspaces, decision trees, DNF formulas, and sparse polynomials. In almost all cases, the property testing algorithm has query complexity independent of $f$, better than the best possible learning algorithm.

## Spring 2009

### Jeffrey Aristoff

On Falling Spheres: the Dynamics of Water Entry, and Descent Along a Flexible Beam
Monday May 18, 2009
2:00pm, Room 2-105
Committee: John Bush (thesis advisor), Aslan Kasimov, Gareth McKinley (Mechanical Engineering)

#### Abstract

This thesis has two parts. In Part I, we present the results of a combined experimental and theoretical investigation of the vertical impact of spheres on a water surface. Particular attention is given to characterizing the shape of the resulting air cavity in the limit where cavity collapse is strongly influenced by surface tension. A parameter study reveals the dependence of the cavity structure on the governing dimensionless groups. A theoretical description is developed to describe the evolution of the cavity shape and yields an analytical solution for the pinch-off time and depth. We also examine low-density spheres that decelerate substantially following impact, and characterize the deceleration rate and resulting change in behavior of the associated water-entry cavities. Theoretical predictions compare favorably with our experimental observations. Finally, we present a theoretical model for the evolution of the splash curtain formed at high speeds, and couple it to the underlying cavity dynamics.

In Part II, we present the results of a combined experimental and theoretical investigation of the motion of a sphere on an inclined flexible beam. A theoretical model based on Euler-Bernoulli beam theory is developed to describe the dynamics, and in the limit where the beam reacts instantaneously to the loading, we obtain exact solutions for the load trajectory and descent time. For the case of an initially horizontal beam, we calculate the period of the resulting oscillations. Theoretical predictions compare favorably with our experimental observations in this quasi-static regime. Inertial effects are also addressed. The time taken for descent along an elastic beam, the elastochrone, is shown to always exceed the classical brachistochrone, the shortest time between two points in a gravitational field.

### Silvia Sabatini

The Topology of GKM Spaces and GKM Fibrations
Tuesday April 28, 2009
3:00pm, Room 1-242
Committee: Victor Guillemin (thesis advisor), Tomasz Mrowka, Catalin Zara (U.Mass-Boston), Susan Tolman (U. Illinois at Urbana-Champaign)

#### Abstract

This thesis primarily consists of results which can be used to simplify the computation of the equivariant cohomology of a GKM space. In particular we investigate the role that equivariant maps play in the computation of these cohomology rings.

Thin the first part of the thesis, we describe some implications of the existence of an equivariant map π between an equivariantly formal $T$-manifold $M$ and a GKM space $\wideƒtilde{M}$. In particular we generalize the Chang-Skjelbred Theorem to this setting and derive some of its consequences. Then we consider the abstract setting of GKM graphs and define a category of objects which we refer to as GKM fiber bundles. For this class of bundles we prove a graph theoretical version of the Serre-Leray Theorem. As an example, we study the projection maps from the complete flag varieties to partial flag varieties from this combinatorial perspective.

In the second part of the thesis we focus on GKM manifolds $M$ which are also $T$-Hamiltonian manifolds. For these spaces, Guillemin and Zara, and Goldin and Tolman, introduced a special basis for $H^T_*(M)$ , associated to a particular choice of a generic component φ of the moment map, the elements of this basis being called canonical classes. Since, for Hamiltonian $T$ spaces, $H_T(M)$ can be viewed as a subring of the equivariant cohomology ring of the fixed point set, it is important to be able to compute the restriction of the elements of this basis to the fixed point set, and we investigate how one can use the existence of an equivariant map to simplify this computation. We also derive conditions under which the formulas we get are integral. Using the above results, we are able to prove, inter alia, positive integral formulas for the equivariant Schubert classes on a complete flag variety of type $A_n$, $B_n$, $C_n$ and $D_n$. (These formulas are new, except in type $A_n$). More generally, we obtain positive integral formulas for the quivariant Schubert classes using fibrations of the complete flag variety over partial flag varieties, and when this fibration is a $\mathbb{C}P^1$-bundle, one gets from these formulas the calculus of divided difference operators.

### Alexey Spiridonov

Pattern-Avoidance in Binary Fillings of Grid Shapes
Monday April 27, 2009
3:00pm, Room 2-143
Committee: Alex Postnikov (thesis advisor), Richard Stanley, Daniel Kleitman

#### Abstract

A grid shape is a set of boxes chosen from a square grid; any Young diagram is an example. We consider a notion of pattern-avoidance for 0-1 fillings of grid shapes, which generalizes permutation pattern-avoidance. A filling avoids some patterns if none of its sub-shapes equal any of the patterns. We focus on patterns that are pairs of 2" × 2" fillings. For some shapes, fillings that avoid specific 2" × 2" pairs are in bijection with totally nonnegative Grassmann cells, or with acyclic orientations of bipartite graphs. We prove a number of results analogous to Wilf-equivalence for these objects—that is, we show that for certain classes of shapes, some pattern-avoiding fillings are equinumerous with others.

### Maksim Maydanskiy

Exotic Symplectic Manifolds from Lefschetz Fibrations
Monday April 27, 2009
1:00pm, Room 4-234
Committee: Denis Auroux (thesis advisor), Paul Seidel, Mohammed Abouzaid

#### Abstract

Stein manifolds are known to symplectic geometers as Liouville domains and are an especially nice class of open symplectic manifolds. I construct, in all odd complex dimensions, pairs of Lioville domains $W0$ and $W1$ which are diffeomorphic to the sphere cotangent bundle with one extra subcritical handle but are not exact symplectomorphic. In fact, while $W0$ is symplectically very similar to the cotangent bundle itself, $W1$ is more unusual; in particular it contains no compact exact Lagrangian submanifolds. Constructions are given by explicit Lefschetz fibrations and the proofs involve calculations of wrapped Floer homologies.

### Yankι Lekili

Broken Lefschetz Fibrations, Lagrangian Matching Invariants and Ozsváth-Szabó Invariants
Monday, April 27, 2009
10:00am, Room 2-142
Committee: Denis Auroux (thesis advisor), Tomasz Mrowka, Paul Seidel

#### Abstract

Broken Lefschetz fibrations are a new way to depict smooth 4-manifolds and to investigate their topology; for instance, Perutz defines invariants of 4-manifolds by counting $J$-holomorphic sections of these fibrations. The first part of this thesis is about the calculus of these objects. In particular, based on earlier results we prove the existence of broken Lefschetz fibrations on any smooth oriented closed 4-manifold and describe certain topological manipulations of these objects, to construct new broken Lefschetz fibration, e.g. with better properties from other ones.

The second part is about Perutz's invariants for broken Lefschetz fibrations, the corresponding invariants for 3-manifolds mapping to $S1$, and relating these invariants to Ozsváth-Szabó's 3- and 4-manifold invariants. Specifically, we prove an isomorphism between two 3-manifold invariants, namely Perutz's quilted Floer homology and Ozsváth-Szabó's Heegaard Floer homology for certain spin$c$ structures. This yields interesting and in a sense simplified geometric interpretations of Ozsváth-Szabó invariants. In particular, we give new calculations of these invariants and other applications, e.g. a proof of Floer's excision theorem in the context of Heegaard Floer homology.

### Victor Yen-Wen Chen

The Gowers Norm in the Testing of Boolean Functions
Thursday April 23, 2009
2:00pm, Room 32G-575
Committee: Madhu Sudan (EECS) (thesis advisor), Peter Shor, Michael Sipser (committee chairman)

### Jacob Bernstein

Conformal and Asymptotic Properties of Embedded Genus-$g$ Minimal Surfaces with One End
Wednesday April 22, 2009
3:00pm, Room 2-136
Committee: Tobias Colding (thesis advisor), Richard Melrose, Tomasz Mrowka

#### Abstract

Using the tools developed by Colding and Minicozzi in their study of the structure of embedded minimal surfaces in $\mathbb{R}^3$, we investigate the conformal and asymptotic properties of complete, embedded minimal surfaces of finite genus and one end. We first present a more geometric proof of the uniqueness of the helicoid than the original, due to Meeks and Rosenberg. That is, the only properly embedded and complete minimal disks in $\mathbb{R}^3$ are the plane and the helicoid. We then extend these techniques to show that any complete, embedded minimal surface with one end and finite topology is conformal to a once-punctured compact Riemann surface. This completes the classification of the conformal type of embedded finite topology minimal surfaces in $\mathbb{R}^3$. Moreover, we show that such surface has Weierstrass data asymptotic to that of the helicoid, and as a consequence is asymptotic to a helicoid (in a Hausdorff sense). As such, we call such surfaces genus-$g$ helicoids. In addition, we sharpen results of Colding and Minicozzi on the shapes of embedded minimal disks in $\mathbb{R}^3$, giving a more precise scale on which minimal disks with large curvature are helicoidal. Finally, we begin to study the finer properties of the structure of genus-$g$ helicoids, in particular showing that the space of genus-one helicoids is compact (after a suitable normalization).

### Jingbin Yin

A q-analogue of Spanning Trees: Nilpotent Transformations over Finite Fields
Monday, April 13, 2009
2:00pm, Room 8-205
Committee: Richard Stanley (thesis advisor), Ira Gessel (Brandeis), Alex Postnikov

#### Abstract

The main result of this work is a $q$-analogue relationship between nilpotent transformations and spanning trees. For example, nilpotent endomorphisms on an $n$-dimensional vector space over $Fq$ is a $q$-analogue of rooted spanning trees of the complete graph $K$. This relationship is based on two similar bijective proofs to calculate the number of spanning trees and nilpotent transformations, respectively.

We also discuss more details about this bijection in the cases of complete graphs, complete bipartite graphs, and cycles. It gives some refinements of the $q$-analogue relationship. As a corollary, we find the total number of nilpotent transformations with some restrictions on Jordan block sizes.

### Liang Xiao

Non-archimedean Differential Modules and Ramification Theory
Monday, April 6, 2009
1:00pm (as part of the STAGE Seminar), Room 2-143
Committee: Kiran Kedlaya (thesis advisor), Bjorn Poonen, Benjamin Brubaker

#### Abstract

In this thesis, I first systematically develop the theory of non-archimedean differential modules, deducing a fundamental theorem about the variation of generic convergent radii of differential modules; it asserts that the log of subsidiary radii of convergence are convex, continuous, and piecewise affine functions of the log of the radii of the polyannuli.

Then I apply this strong tool to the ramification theory and deduce the fundamental result, Hasse-Arf theorem, for ramification filtrations defined by Abbes and Saito. Also, we include a comparison theorem to differential conductors and Borger's conductors in the equal characteristic case.

Finally, I globalize this construction and give a new understanding of the ramification theory for smooth varieties, which provides some new insight to the global class field theory. We end the thesis with a series of conjectures as a starting point of a long going project aiming to understand global ramification.

### Salman Abolfathe Beikidezfuli

Quantum Proof Systems and Entanglement Theory
Wednesday April 1, 2009
3:00pm, Room 56-114
Committee: Peter Shor (thesis advisor), Daniel Kleitman, Scott Aaronson (EECS)

#### Abstract

Quantum complexity theory is important from the point of view of not only theory of computation but also quantum information theory. In particular, quantum multi-prover interactive proof systems are defined based on complexity theory notions, while their characterization can be formulated using LOCC operations. On the other hand, the main resource in quantum information theory is entanglement, which can be considered as a monotonic decreasing quantity under LOCC maps. Indeed, any result in quantum proof systems can be translated to entanglement theory, and vice versa. In this thesis I mostly focus on quantum Merlin-Arthur games as a proof system in quantum complexity theory.

I present a new complete problem for the complexity class QMA. I also show that computing both the Holevo capacity and the minimum output entropy of quantum channels are NP-hard. Then I move to the multiple-Merlin-Arthur games and show that assuming some additivity conjecture for entanglement of formation, we can amplify the gap in QMA(2) protocols. Based on the same assumption, I show that the QMA($k$)-hierarchy collapses to QMA(2). I also prove that QMA$log$(2), which is defined the same as QMA(2) except that the size of witnesses is logarithmic, with the gap $n$-(3+ε) contains NP. Finally, motivated by the previous results, I show that the positive partial transpose test gives no bound on the trace distance of a given bipartite state from the set of separable states.

### Alexander Ritter

The Novikov Theory for Symplectic Cohomology and Exact Lagrangian Embeddings
Friday, March 20, 2009
2:30pm, Room 2-143
Committee: Paul Seidel (thesis advisor), Tomasz Mrowka, Denis Auroux

#### Abstract

Given an exact symplectic manifold, can we find topological constraints to the existence of exact Lagrangian submanifolds?

I developed an approach using symplectic cohomology which provides such conditions for exact Lagrangians inside cotangent bundles and inside ALE hyperkähler spaces. For example, the only exact Lagrangians inside ALE hyperkähler spaces must be spheres.

The vanishing of symplectic cohomology is an obstruction to the existence of exact Lagrangians. In the above applications even though the ordinary symplectic cohomology does not vanish, one can prove that a Novikov homology analogue for symplectic cohomology does vanish.

### Christopher Davis

The Overconvergent de Rham-Witt Complex
Monday, March 2, 2009
1:00pm (as part of the STAGE Seminar), Room 2-143
Committee: Kiran Kedlaya (thesis advisor), Abhinav Kumar, Clark Barwick (Harvard)

#### Abstract

We will begin by briefly reviewing Monsky-Washnitzer cohomology and the de Rham-Witt complex. We will then define the overconvergent de Rham-Witt complex $W\dagger\Omega_\overline{C}$ for a smooth affine variety over a perfect field in characteristic $p$. It is a subcomplex of the Rham-Witt complex. We show that, after tensoring with $\mathbb{Q}$, its cohomology agrees with the Monsky-Washitzer cohomology. One advantage of our construction is that it does not involve a choice of lift to characteristic zero.

To prove that the cohomology groups are the same, we define a comparison map
$t_F$ : $\Omega_{C\dagger} \rightarrow W^\dagger\Omega_{\overline{C}}$

We cover our smooth affine $\overline{C}$ with certain special affines $\overline{B}$. For these particular affines, we decompose $W^\dagger\Omega_\overline{B}$ into an integral part and a fractional part and then show that the integral part is isomorphic to the Monsky-Washnitzer complex and that the fractional part is acyclic. We deduce our result for the more general $\overline{C}$ from a homotopy argument and the fact that our complex is a Zariski sheaf.