Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 1967. / Vita. / Includes bibliographical references (leaf 8). / by Harvey Martin Friedman. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2007. / Includes bibliographical references (p. 81-85). / In the first part, we present a family of entanglement purification protocols that generalize four previous methods, namely the recurrence method, the modified recurrence method, and the two methods proposed by Maneva-Smolin and Leung-Shor. We will show that this family of protocols have improved yields over a wide range of initial fidelities F, and hence imply new lower bounds on the quantum capacity assisted by two-way classical communication of the quantum depolarizing channel. In particular, we show that the yields of these protocols are higher than the yield of universal hashing for F less than 0.99999 and as F goes to 1. In the second part, we define, for any quantum discrete memoryless channel, quantum entanglement capacity with classical feedback, a quantity that lies between two other well-studied quantities. These two quantities - namely the quantum capacity assisted by two-way classical communication and the quantum capacity with classical feedback - are widely conjectured to be different. We then present adaptive protocols for this newly-defined quantity on the quantum depolarizing channel. These protocols in turn imply new lower bounds on the quantum capacity with classical feedback. / by Alan W. Leung. / Ph.D.

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.