Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 1994. / Includes bibliographical references (leaves 57-58). / by Mohamed Jamil Baddoura. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2011. / Cataloged from PDF version of thesis. / Includes bibliographical references (p. 163-170). / We present two recent parallel programming languages, PetaBricks and Julia, and demonstrate how we can use these two languages to re-examine classic numerical algorithms in new approaches for high-performance computing. PetaBricks is an implicitly parallel language that allows programmers to naturally express algorithmic choice explicitly at the language level. The PetaBricks compiler and autotuner is not only able to compose a complex program using fine-grained algorithmic choices but also find the right choice for many other parameters including data distribution, parallelization and blocking. We re-examine classic numerical algorithms with PetaBricks, and show that the PetaBricks autotuner produces nontrivial optimal algorithms that are difficult to reproduce otherwise. We also introduce the notion of variable accuracy algorithms, in which accuracy measures and requirements are supplied by the programmer and incorporated by the PetaBricks compiler and autotuner in the search of optimal algorithms. We demonstrate the accuracy/performance trade-offs by benchmark problems, and show how nontrivial algorithmic choice can change with different user accuracy requirements. Julia is a new high-level programming language that aims at achieving performance comparable to traditional compiled languages, while remaining easy to program and offering flexible parallelism without extensive effort. We describe a problem in large-scale terrain data analysis which motivates the use of Julia. We perform classical filtering techniques to study the terrain profiles and propose a measure based on Singular Value Decomposition (SVD) to quantify terrain surface roughness. We then give a brief tutorial of Julia and present results of our serial blocked SVD algorithm implementation in Julia. We also describe the parallel implementation of our SVD algorithm and discuss how flexible parallelism can be further explored using Julia. / by Yee Lok Wong. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2011. / 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. 205-214). / Modern biology is being remade by a dizzying array of new technologies, a deluge of data, and an increasingly strong reliance on computation to guide and interpret experiments. In two areas of biology, computational methods have become central: predicting and designing the structure of biological molecules and inferring function from molecular evolution. In this thesis, I develop a number of algorithms for problems in these areas and combine them with experiment to provide biological insight. First, I study the problem of designing RNA sequences that fold into specific structures. To do so I introduce a novel computational problem on Hidden Markov Models (HMMs) and Stochastic Context Free Grammars (SCFGs). I show that the problem is NP-hard, resolving an open question for RNA secondary structure design, and go on to develop a number of approximation approaches. I then turn to the problem of inferring function from evolution. I develop an algorithm to identify regions in the genome that are serving two simultaneous functions: encoding a protein and encoding regulatory information. I first use this algorithm to find microRNA targets in both Drosophila and mammalian genes and show that conserved microRNA targeting in coding regions is widespread. Next, I identify a novel phenomenon where an accumulation of sequence repeats leads to surprisingly strong microRNA targeting, demonstrating a previously unknown role for such repeats. Finally, I address the problem of detecting more general conserved regulatory elements in coding DNA. I show that such elements are widespread in Drosophila and can be identified with high confidence, a result with important implications for understanding both biological regulation and the evolution of protein coding sequences. / by Michael Schnall-Levin. / Ph.D.

Thesis (Sc. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 1996. / Includes bibliographical references (leaves 66-68). / by Siqian He. / Sc.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 1993. / Includes bibliographical references (p. 61-62). / by Richard A. Scott. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2005. / Includes bibliographical references (p. 165-171). / In an online decision problem, an algorithm performs a sequence of trials, each of which involves selecting one element from a fixed set of alternatives (the "strategy set") whose costs vary over time. After T trials, the combined cost of the algorithm's choices is compared with that of the single strategy whose combined cost is minimum. Their difference is called regret, and one seeks algorithms which are efficient in that their regret is sublinear in T and polynomial in the problem size. We study an important class of online decision problems called generalized multi- armed bandit problems. In the past such problems have found applications in areas as diverse as statistics, computer science, economic theory, and medical decision-making. Most existing algorithms were efficient only in the case of a small (i.e. polynomial- sized) strategy set. We extend the theory by supplying non-trivial algorithms and lower bounds for cases in which the strategy set is much larger (exponential or infinite) and the cost function class is structured, e.g. by constraining the cost functions to be linear or convex. As applications, we consider adaptive routing in networks, adaptive pricing in electronic markets, and collaborative decision-making by untrusting peers in a dynamic environment. / by Robert David Kleinberg. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2011. / Cataloged from PDF version of thesis. / Includes bibliographical references (p. 187-198). / We study three problems arising from different areas of combinatorial optimization. We first study the matroid secretary problem, which is a generalization proposed by Babaioff, Immorlica and Kleinberg of the classical secretary problem. In this problem, the elements of a given matroid are revealed one by one. When an element is revealed, we learn information about its weight and decide to accept it or not, while keeping the accepted set independent in the matroid. The goal is to maximize the expected weight of our solution. We study different variants for this problem depending on how the elements are presented and on how the weights are assigned to the elements. Our main result is the first constant competitive algorithm for the random-assignment random-order model. In this model, a list of hidden nonnegative weights is randomly assigned to the elements of the matroid, which are later presented to us in uniform random order, independent of the assignment. The second problem studied is the jump number problem. Consider a linear extension L of a poset P. A jump is a pair of consecutive elements in L that are not comparable in P. Finding a linear extension minimizing the number of jumps is NP-hard even for chordal bipartite posets. For the class of posets having two directional orthogonal ray comparability graphs, we show that this problem is equivalent to finding a maximum independent set of a well-behaved family of rectangles. Using this, we devise combinatorial and LP-based algorithms for the jump number problem, extending the class of bipartite posets for which this problem is polynomially solvable and improving on the running time of existing algorithms for certain subclasses. The last problem studied is the one of finding nonempty minimizers of a symmetric submodular function over any family of sets closed under inclusion. We give an efficient O(ns)-time algorithm for this task, based on Queyranne's pendant pair technique for minimizing unconstrained symmetric submodular functions. We extend this algorithm to report all inclusion-wise nonempty minimal minimizers under hereditary constraints of slightly more general functions. / by José Antonio Soto. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 1994. / Includes bibliographical references (leaf 51). / by Eric Kendall Babson. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2011. / Cataloged from PDF version of thesis. / Includes bibliographical references (p. 79-80). / This thesis consists of two parts. The first part applies a probabilistic approach to the study of the Wright-Fisher equation, an equation which is used to model demographic evolution in the presence of diffusion. The fundamental solution to the Wright-Fisher equation is carefully analyzed by relating it to the fundamental solution to a model equation which has the same degeneracy at one boundary. Estimates are given for short time behavior of the fundamental solution as well as its derivatives near the boundary. The second part studies the probabilistic extensions of the classical Cauchy functional equation for additive functions both in finite and infinite dimensions. The connection between additivity and linearity is explored under different circumstances, and the techniques developed in the process lead to results about the structure of abstract Wiener spaces. Both parts are joint work with Daniel W. Stroock. / by Linan Chen. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2011. / Cataloged from PDF version of thesis. / Includes bibliographical references (p. 55-56). / In this thesis, we investigate the birational geometry of the space of rational curves in various homogeneous spaces, with a focus on the quasi-map compactification induced by the Quot and Hyperquot functors. We first study the birational geometry of the Quot scheme of sheaves on P1 via techniques from the Mori program, explicitly describing its associated cones of ample and effective divisors as well as the various Mori chambers within the latter. We compute the base loci of all effective divisors, and give a conjectural description of the induced birational models. We then partially extend our results to the Hyperquot scheme of sheaves on P', which gives the analogous compactification for rational curves in flag varieties. We fully describe the cone of ample divisors in all cases and the cone of effective divisors in certain ones, but only claim a partial description of the latter in general. / by Kartik Venkatram. / Ph.D.