Thesis (M.S.)--Massachusetts Institute of Technology, Dept. of Mathematics, 1973. / Vita. / Bibliography: leaves 20-21. / M.S.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2005. / Includes bibliographical references (leaves 103-106). / (cont.) Packing/Covering problems, we prove upper and lower bounds on the adaptivity gap depending on the dimension. We also design polynomial-time algorithms achieving near-optimal approximation guarantees with respect to the adaptive optimum. Finally, we prove complexity-theoretic results regarding optimal adaptive policies. These results are based on a connection between adaptive policies and Arthur-Merlin games which yields PSPACE-hardness results for numerous questions regarding adaptive policies. / In this thesis we study a variety of combinatorial problems with inherent randomness. In the first part of the thesis, we study the possibility of covering the solutions of an optimization problem on random subgraphs. The motivation for this approach is a situation where an optimization problem needs to be solved repeatedly for random instances. Then we seek a pre-processing stage which would speed-up subsequent queries by finding a fixed sparse subgraph covering the solution for a random subgraph with high probability. The first problem that we investigate is the minimum spanning tree. Our essential result regarding this problem is that for every graph with edge weights, there is a set of O(n log n) edges which contains the minimum spanning tree of a random subgraph with high probability. More generally, we extend this result to matroids. Further, we consider optimization problems based on the shortest path metric and we find covering sets of size 0(n(̂1+2/c) log2̂ n) that approximate the shortest path metric of a random vertex-induced subgraph within a constant factor of c with high probability. In the second part, we turn to a model of stochastic optimization, where a solution is built sequentially by selecting a collection of "items". We distinguish between adaptive and non-adaptive strategies, where adaptivity means being able to perceive the precise characteristics of chosen items and use this knowledge in subsequent decisions. The benefit of adaptivity is our central concept which we investigate for a variety of specific problems. For the Stochastic Knapsack problem, we prove constant upper and lower bounds on the "adaptivity gap" between optimal adaptive and non-adaptive policies. For more general Stochastic / by Jan Vondrák. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 1996. / Includes bibliographical references (leaves 85-87). / by Leonid I. Korogodsky. / Ph.D.

Thesis: Ph. D., Massachusetts Institute of Technology, Department of Mathematics, 2018. / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 205-213). / Community recovery is a major challenge in data science and computer science. The goal in community recovery is to find the hidden clusters from given relational data, which is often represented as a labeled hyper graph where nodes correspond to items needing to be labeled and edges correspond to observed relations between the items. We investigate the problem of exact recovery in the class of statistical models which can be expressed in terms of graphical channels. In a graphical channel model, we observe noisy measurements of the relations between k nodes while the true labeling is unknown to us, and the goal is to recover the labels correctly. This generalizes both the stochastic block models and spiked tensor models for principal component analysis, which has gained much interest over the last decade. We focus on two aspects of exact recovery: statistical limits and efficient algorithms achieving the statistic limit. For the statistical limits, we show that the achievability of exact recovery is essentially determined by whether we can recover the label of one node given other nodes labels with fairly high probability. This phenomenon was observed by Abbe et al. for generic stochastic block models, and called "local-to-global amplification". We confirm that local-to-global amplification indeed holds for generic graphical channel models, under some regularity assumptions. As a corollary, the threshold for exact recovery is explicitly determined. For algorithmic concerns, we consider two examples of graphical channel models, (i) the spiked tensor model with additive Gaussian noise, and (ii) the generalization of the stochastic block model for k-uniform hypergraphs. We propose a strategy which we call "truncate-and-relax", based on a standard semidefinite relaxation technique. We show that in these two models, the algorithm based on this strategy achieves exact recovery up to a threshold which orderwise matches the statistical threshold. We complement this by showing the limitation of the algorithm. / by Chiheon Kim. / Ph. D.

Thesis (M.S.) Massachusetts Institute of Technology. Dept. of Mathematics, 1951. / by Harold S. Shapiro. / M.S.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2012. / This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / Cataloged from student submitted PDF version of thesis. / Includes bibliographical references (p. 71-72). / Boij-Söderberg theory is the study of two cones: the first is the cone of graded Betti tables over a polynomial ring, and the second is the cone of cohomology tables of coherent sheaves over projective space. Each cone has a triangulation induced from a certain partial order. Our first result gives a module-theoretic interpretation of this poset structure. The study of the cone of cohomology tables over an arbitrary polarized projective variety is closely related to the existence of an Ulrich sheaf, and our second result shows that such sheaves exist on the class of Schubert degeneracy loci. Finally, we consider the problem of classifying the possible ranks of Betti numbers for modules over a regular local ring. / by Steven V Sam. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2010. / Cataloged from PDF version of thesis. / Includes bibliographical references (p. 49-50). / We begin the study of unitary representations in the lowest weight category of rational Cherednik algebras of complex reflection groups. We provide the complete classification of unitary representations for the symmetric group, the dihedral group, as well as some additional partial results. We also study the unitary representations of Hecke algebras of complex reflection groups and provide a complete classification in the case of the symmetric group. We conclude that the KZ functor defined in [16] preserves unitarity in type A. Finally, we formulate a few conjectures concerning the classification of unitary representations for other types and the preservation of unitarity by the KZ functor and the restriction functors defined in [2]. / by Emanuel Stoica. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 1989. / Includes bibliographical references (leaf 33). / by Dorshka Wylie. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2004. / Includes bibliographical references (p. 83-85). / Consider the unnormalized Ricci flow ...Richard Hamilton showed that if the curvature operator is uniformly bounded under the flow for all times ... then the solution can be extended beyond T. In the thesis we prove that if the Ricci curvature is uniformly bounded under the flow for all times ... then the curvature tensor has to be uniformly bounded as well. In particular, this means that if the Ricci tensor stays uniformly bounded up to a finite time T, a Ricci flow can not develop a singularity at T. We will give two different proofs of that result. One of them relies on Hamilton's estimates on distance changes along the flow and the other one relies on the identities for reduced distances and the monotonicity formula for reduced volumes that has been introduced and proved by Perelman in [29]. Consider the Ricci flow ... on a closed, n-dimensional manifold M. Assume that a solution of the flow exists for all times ... and that the curvatures and the diameters are uniformly bounded along the flow. We will prove that for every sequence ... there exists a subsequence such that g(ti + t) converges to a metric h(t) and h(t) is a Ricci soliton. We will also prove that if one of the limit solitons is integrable, then a soliton that we get in the limit is unique up to diffeomorphisms and the convergence toward it is exponential. / (cont.) We will also prove that in an arbitrary dimension, for a given Kähler-Ricci flow with uniformly bounded Ricci curvatures, for every sequence of times ti converging to infinity, there exists a subsequence such that ... and the convergence is smooth outside a singular set (which is a set of codimension at least 4). Moreover, g(t) is a solution of the flow off the singular set. In the case of a complex dimension 2, for any sequence of times converging to infinity we can find a subsequence of times such that we have a convergence toward a Kähler-Ricci soliton, away from finitely many isolated singularities. / by NataÅ¡a Å eÅ¡um. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2005. / 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. 81-82). / In the framework of fibred cusp operators on a manifold X associated to a boundary fibration ... , the homotopy groups of the space ... of invertible smoothing perturbations of the identity are computed in terms of the K-theory of T*Y . It is shown that there is a periodicity, namely the odd and the even homotopy groups are isomorphic among themselves. To obtain this result, one of the important steps is the description of the index of a Fredholm smoothing perturbation of the identity in terms of an associated K-class in K ... / by Frédéric Rochon. / Ph.D.