Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2008. / In title on title page, "[epsilon]" appears as lower case Greek letter. / Includes bibliographical references (p. 49-50). / The quantum information theory is the counterpart of the classical information theory in quantum computation, and it has raised many questions regarding the transmission and security of the information in quantum computers. This thesis studies the efficiency of such processes and contributes to two separate area of quantum information theory. The first half of this thesis presents a communication protocol for the erasure channel assisted by backward classical communication, which achieves a significantly better rate than the best prior result. In addition, we reduce the proof of a new upper bound for the capacity of the channel to a conjecture. The proposed upper bound is smaller than the capacity of the erasure channel when it is assisted by two-way classical communication. Hence, the proof of the separation between quantum capacities assisted by backward classical communication and two-way classical communication is also reduced to the conjecture. The second half of this thesis studies the construction of an c-randomizing map that uses Pauli operators. An e-randomizing map transforms any n-qubit state to an almost random state - a state that is within e-distance of the completely random state, in the trace norm. We show that at least O( Ta ) Pauli operators are required for the construction of an e-randomizing map. This proves the lower bound on the length of a private key required for a private communication as min {2n, n+log23 log(1/c)}+O(1). Our result matches the previous upper bound of n + 21og(1/c) + 0(1) for the optimal key length, in the order of n. / by Joungkeun Lim. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 1987. / Vita. / Includes bibliographical references (v. 2, p. 470-478). / by Jeffrey R. Sachs. / Ph.D.

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.