Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 1997. / Includes bibliographical references (p. 163-170). / by Matthew Andrews. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2009. / Includes bibliographical references (p. 147-151). / Markov random field (MRF) model provides an elegant probabilistic framework to formulate inter-dependency between a large number of random variables. In this thesis, we present a new approximation algorithm for computing Maximum a Posteriori (MAP) and the log-partition function for arbitrary positive pair-wise MRF defined on a graph G. Our algorithm is based on decomposition of G into appropriately chosen small components; then computing estimates locally in each of these components and then producing a good global solution. We show that if either G excludes some finite-sized graph as its minor (e.g. planar graph) and has a constant degree bound, or G is a polynoinially growing graph, then our algorithm produce solutions for both questions within arbitrary accuracy. The running time of the algorithm is linear on the number of nodes in G, with constant dependent on the accuracy. We apply our algorithm for MAP computation to the problem of learning the capacity region of wireless networks. We consider wireless networks of nodes placed in some geographic area in an arbitrary manner under interference constraints. We propose a polynomial time approximate algorithm to determine whether a, given vector of end-to-end rates between various source-destination pairs can be supported by the network through a combination of routing and scheduling decisions. Lastly, we investigate the problem of computing loss probabilities of routes in a stochastic loss network, which is equivalent to computing the partition function of the corresponding MR.F for the exact stationary distribution. / (cont.) We show that the very popular Erlang approximation provide relatively poor performance estimates, especially for loss networks in the critically loaded regime. Then we propose a novel algorithm for estimating the stationary loss probabilities, which is shown to always converge, exponentially fast, to the asymptotically exact results. / by Kyomin Jung. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2010. / Cataloged from PDF version of thesis. / Includes bibliographical references (p. 40-41). / This thesis consists of two parts. In the first part, we start by investigating the classical permutohedra as Minkowski sums of the hypersimplices. Their volumes can be expressed as polynomials whose coefficients - the mixed Eulerian numbers - are given by the mixed volumes of the hypersimplices. We build upon results of Postnikov and derive various recursive and combinatorial formulas for the mixed Eulerian numbers. We generalize these results to arbitrary root systems [fee], and obtain cyclic, recursive and combinatorial formulas for the volumes of the weight polytopes ([fee]-analogues of permutohedra) as well as the mixed [fee]-Eulerian numbers. These formulas involve Cartan matrices and weighted paths in Dynkin diagrams, and thus enable us to extend the theory of mixed Eulerian numbers to arbitrary matrices whose principal minors are invertible. The second part deals with the study of certain patterns in standard Young tableaux of shifted shapes. For the staircase shape, Postnikov found a bijection between vectors formed by the diagonal entries of these tableaux and lattice points of the (standard) associahedron. Using similar techniques, we generalize this result to arbitrary shifted shapes. / by Dorian Croitoru. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Department of Mathematics, 2013. / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 37-38). / Let X be a regular arithmetic curve or point (meaning a regular separated scheme of finite type over Z which is connected and of Krull dimension </= 1). We define a compactly-supported variant Kc(X) of the algebraic K-theory spectrum K(X), and establish the basic functoriality of Kc. Briefly, K, behaves as if it were dual to K. Then we give this duality some grounding: for every prime t invertible on X, we define a natural l-adic pairing between Kc(X) and K(X). This pairing is of an explicit homotopy-theoretic nature, and reflects a simple relation between spheres, tori, and real vector spaces. Surprisingly, it has the following two properties: first (a consequence of work of Rezk), when one tries to compute it the e-adic logarithm inevitably appears; and second, it can be used to give a new description of the global Artin map, one which makes the Artin reciprocity law manifest. / by Dustin Clausen. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2002. / Includes bibliographical references (p. 151-154) and index. / I analyze packet routing on unidirectional ring networks, with an eye towards establishing bounds on the expected length of the queues. Suppose we route packets by a greedy "hot potato" protocol. If packets are inserted by a Bernoulli process and have uniform destinations around the ring, and if the nominal load is kept fixed, then I can construct an upper bound on the expected queue length per node that is independent of the size of the ring. If the packets only travel one or two steps, I can calculate the exact expected queue length for rings of any size. I also show some stability results under more general circumstances. If the packets are inserted by any ergodic hidden Markov process with nominal loads less than one, and routed by any greedy protocol, I prove that the ring is ergodic. / by William F. Bradley. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2006. / Includes bibliographical references (p. 255-266). / A crystal lattice with a small miscut from the plane of symmetry has a surface which consists of a series of atomic height steps separated by terraces. If the surface of this crystal is not in equilibrium with the surrounding medium, then its evolution is strongly mediated by the presence of these steps, which act as sites for attachment and detachment of diffusing adsorbed atoms ('adatoms'). In the absence of material deposition and evaporation, steps move in response to two main physical effects: line tension, which is caused by curvature of the step edge, and step-step interactions which can arise because of thermal step fluctuations, or elastic effects. This thesis focuses on axisymmetric crystals, with the result that the position of a step is uniquely described by a single scalar variable, and the step positions obey a coupled system of "step-flow" Ordinary Differential Equations (step flow ODEs). Chapter 2 of this thesis concentrates on the derivation and numerical solution of these equations, and their properties in the limits of slow adatom terrace diffusion and slow adatom attachment-detachment. Chapter 3 focuses on the analysis carried out by Margetis, Aziz and Stone ('MAS') [78] on a Partial Differential Equation (PDE) description of surface evolution. / (cont.) Here, the crystal is also axisymmetric and has a single macroscopically flat region, a facet. It is discovered that the boundary condition of Step Chemical Potential Continuity, first suggested by Spohn [109] yields results that are inconsistent with the scalings predicted by the MAS analysis and with results from the step flow ODEs. The 'step drop' condition suggested by Israeli and Kandel [50] is implemented instead, and is shown to give good agreement with the results from the step flow ODEs. Chapters 4 and 5 explore the evolution of algebraic profiles: instead of starting with steps that are equally spaced, the step radii are initialized as a more general algebraic function of the height. In these two chapters, results are presented which involve approximate self-similarity of the profiles, a stability analysis of small perturbations, and quantification of decay rates. Chapter 6 of this thesis details the numerical procedure used to integrate the step flow equations. A 'multi-adaptive' time integrator is used where different time steps are taken for different components of the solution. This procedure has benefits over a standard integrator, because when a few steps cluster tightly together, these steps (and these steps only) become very stiff to integrate. / (cont.) Whereas the inner most steps in the structure undergo a rapid motion, the majority of steps which are sufficiently far away from the facet, move relatively slowly and exhibit smooth behaviour in time. Using the same time step for all components in the solution is therefore quite inefficient. This chapter discusses the concept of "local stiffness", and how the motion of the inner most steps is handled. / by Pak-Wing Fok. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2008. / This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / Includes bibliographical references (p. 135-137). / In this thesis, we show that single-petaled K-types and quasi-single-petaled K-types for reductive Lie groups generalize petite K-types for split groups. First, we prove that a Weyl group algebra element represents the action of the long intertwining operator for each single-petaled K-type, and then we demonstrate that a Weyl group algebra element represents a part of the long intertwining operator for each quasi-single-petaled K-type. We classify irreducible Weyl group representations realized by quasi-single-petaled K-types for classical groups. This work proves that every irreducible Weyl group representation is realized by quasi-single-petaled K-types for SL(n;C), SL(n;R), SU(m; n), SO(m; n), and Sp(n;R). / by Jerin Gu. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2002. / Includes bibliographical references (p. 173-180). / This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / The central focus of my thesis is to study the instability jets of various complexity by analyzing the linear and nonlinear dynamics. We applied this methodology to four different situations in order to learn the following. First, what asymmetries develop between cyclones and anticyclones because of finite variations in the free surface? Second, how is the stability of a jet flowing along a topographic step altered by the topography beneath? Third, can parametric instability arise in shear flows? Fourth, can an idealized model of a tidally and topographically forced coastal jet develop instabilities, and if so, can these instabilities become turbulent? / by Francis Joseph Poulin. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2001. / Includes bibliographical references (p. 161-165). / Solar activity, as indexed by sunspots, has a cycle of length varying from about 9 to 13 years. Statisticians have fitted several models to predict sunspot numbers one year ahead. We instead focus on predicting the magnitudes of the next cycle maximum, the next cycle minimum, the time from the initial minimum of a cycle to its maximum, called the rise time, and the time from a cycle maximum to the next cycle minimum, called the fall time. The predictions are based on sunspot numbers just far enough into a new cycle to establish that a cycle has started. We propose parsimonious regression models for the maximum and rise time. For the fall time and minimum we propose crude models, based on the sample means and variances for all past cycles. We compare our models to simulation results for many models we found in the literature including autoregressive (AR) models, subset AR (SAR) models, and related nonlinear models including a threshold AR model, transformed by squaring (TTAR model), a bilinear model, a so-called ASTAR model, and a neural network (CNAR) model. We also consider a model proposed by solar physicists, based on a functional form for cycles. / (cont.) Numerical results show that among all the models considered for sunspot numbers, our regression models give the smallest MSEs (mean-square errors) for the maxima, and our crude models give the smallest MSEs for the minima. For fall times our crude model has the second-smallest MSE after CNAR. ASTAR does very well for modeling the rise times. Observations of the sun have become progressively more accurate, but we found that giving higher weight to more recent observations gave worse results. Among the model selection criteria we tried for the autoregressive and regression models, the two that worked best as judged by cross-validations were the well-known Akaike Information Criterion and a modification of the G. Schwarz BIC criterion called BIC* due to D. and J. Haughton and A. Izenman. / by Li He. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2001. / Includes bibliographical references (p. 81-83). / Let G be a complex semi-simple and classical Lie group. The notion of a Lagrangian covering can be used to extend the method of polarizing a nilpotent coadjoint orbit to obtain a unitary representation of G. W. Graham and D. Vogan propose such a construction, relying on the notions of orbital varieties and admissible orbit data. The first part of the thesis seeks to understand the set of orbital varieties contained in a given nipotent orbit. Starting from N. Spaltenstein's parameterization of the irreducible components of the variety of flags fixed by a unipotent, we produce a parameterization of the orbital varieties lying in the corresponding fiber of the Steinberg map. The parameter set is the family of standard Young or domino tableau of a given shape. The key to the proof is understanding certain closed cycles as defined by D. Garfinkle. This parameterization is particularly useful; it provides a method of determining the r-invariant of each orbital variety, as well as a way of relating an orbital variety in any classical group to one lying in type A. / (cont.) The second part of the thesis addresses the representations V(V, ir) constructed by Graham and Vogan. A natural question is how well the V(V, 7r) approximate the set of unipotent representations that ought to be attached to the nilpotent orbit 0. The answer is promising in the setting of spherical orbits. When it is possible to carry out the Graham-Vogan construction, the corresponding infinitesimal character lies in the set of characters suggested by W. M. McGovern. Furthermore, we show that it is possible to carry out the Graham-Vogan construction for a suffient number of orbital varieties to account for all the infinitesimal characters attached to 0 by McGovern. / by Thomas Pietraho. / Ph.D.