Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2004. / Includes bibliographical references (p. 207-223). / The work presented in this thesis falls under the broad umbrella of combinatorics of Erd's type. We describe diverse facets of interplay between geometry and combinatorics and consider several questions about existence of structures in various combinatorial settings. We make contributions to specific problems in combinatorial geometry, Ramsey theory and graph theory. We first study extremal questions in geometric graph theory, that is, the existence of collections of edges with a specified crossing pattern in drawings of graphs in the plane with sufficiently many edges. Among other results, we prove that any drawing of a graph on n vertices and Cn edges, where C is a sufficiently large constant, contains each of the following crossing patterns: (1) three pairwise crossing edges, (2) two edges that cross and are crossed by k other edges, (3) an edge crossed by four other edges. In the latter, we show that C = 5.5 is the best possible constant, which, through Szekely's method, gives the best known value for a constant in the well known "Crossing Lemma" due to Ajtai, Chvatal, Leighton, Newborn and Szemeredi. After relaxing graph planarity in several ways, we proceed to study ... the maximum number of edges in a drawing of a graph on n vertices without self-crossing copy of C4, the cycle of four vertices. We prove that ... The importance of this and the above mentioned results comes from numerous applications of "Crossing Lemma" and the bounds on ... in discrete and computational geometry (incidence and Gallai-Sylvester type problems, k-set problems, / (cont.) the distinct distances and the unit distance problems of Erd6s, problems on arrangements of circles and pseudo-parabolas, questions on parametric and kinetic minimum spanning trees), number theory, and the VLSI design. Next, we initiate a new trend in Ramsey theory, which can be categorized as the rainbow Ramsey theory. Drawing a parallel with Moztkin's statement that "complete disorder is impossible", we prove the existence of rainbow/hetero-chromatic structures in a colored universe, under certain density conditions on the coloring. Hence, we provide several striking examples supporting the new philosophy that complete disorder is unavoidable as well. In particular, we prove that every 3-coloring of the color classes being equinumerous, contains a rainbow 3-term arithmetic progression. We also consider rainbow counterparts of other classical theorems in Ramsey theory, such as Rado's and Hales-Jewett theorem. Additionally, we refute one geometric strengthening of van der Waerden's theorem, thus, answering an open problem posed by Pach. We continue with two classical problems in Euclidean Ramsey theory: (1) Hadwiger-Nelson problem on the chromatic number of Rd and (2) the empty convex hexagon question of Erd6s. We prove that the chromatic number of R3 is at most 15, improving the previous bound of 18, due to Coulson. Regarding the latter question, which is one of the most notorious open problem in combinatorial geometry, we discover interesting relations on the numbers Xk(P) of empty convex k-gons in an n-element planar point set P ... / by Radoš Radoičić. / Ph.D.

Thesis (M.S.)--Massachusetts Institute of Technology, Dept. of Mathematics, 1953. / Includes bibliographical references (leaf [24].) / by Anatol W. Holt. / M.S.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2010. / Cataloged from PDF version of thesis. / Includes bibliographical references (p. 118-128). / This thesis consists of five essays on evolutionary dynamics. In Chapters 1 and 2, we study the evolution of trust from the perspective of game theory. In the trust game, two players have a chance to win a sum of money. The "investor" begins with one monetary unit. She gives a fraction of that unit to the "trustee." The amount she gives is multiplied by a factor greater than one. The trustee then returns a fraction of what he receives to the investor. In a non-repeated game, a rational trustee will return nothing. Hence, a rational investor will give nothing. In behavioral experiments, however, humans exhibit significant levels of trust and trustworthiness. Here we show that these predispositions may be the result of evolutionary adaptations. We find that when investors have information about trustees, investors become completely trusting and trustees assume the minimum level of trustworthiness that justifies that trust. "Reputation" leads to efficient outcomes as the two players split all the possible payoff from the game, but the trustee captures most of the gains: "seller" reputation helps "sellers" more than it helps "buyers." Investors can capture more of the surplus if they are collectively irrational: they can demand more from trustees than is rational, or their sensitivity to information about trustees can be dulled. Collective investor irrationality surprisingly leads to higher payoffs for investors, but each investor has an incentive to deviate from this behavior and act more rationally. Eventually investors evolve to be highly rational and lose the gains their collective behavior had earned them: irrationality is a public good in the trust game. Next, we describe two evolutionarily robust mechanisms for achieving efficient outcomes that favor the investor while still compensating trustees for the value of their agency. In the first mechanism, "comparison shopping," investors compare limited information about various trustees before committing to a transaction. Comparing just two trustees at the beginning of each interaction is enough to achieve a split desirable to the investor, even when information about trustees is only partially available. In the other mechanism, a second layer of information is added so that trustees sometimes know what rates of return investors desire. The trust game then becomes similar to an ultimatum game, and positive investor outcomes can be reached once this second type of information is sufficiently pervasive. In Chapter 3, we study the origin of evolution and replication. We propose "prelife" and "prevolution" as the logical precursors of life and evolution. Prelife generates sequences of variable length. Prelife is a generative chemistry that proliferates information and produces diversity without replication. The resulting "prevolutionary dynamics" have mutation and selection. We propose an equation that allows us to investigate the origin of evolution. In one limit, this "originator equation" gives the classical selection equation. In the other limit, we obtain "prelife." There is competition between life and prelife and there can be selection for or against replication. Simple prelife equations with uniform rate constants have the property that longer sequences are exponentially less frequent than shorter ones. But replication can reverse such an ordering. As the replication rate increases, some longer sequences can become more frequent than shorter ones. Thus, replication can lead to "reversals" in the equilibrium portraits. We study these reversals, which mark the transition from prelife to life in our model. If the replication potential exceeds a critical value, then life replicates into existence. We continue our study of replication in Chapter 4, taking a more concrete, chemistry-oriented approach. Template-directed polymerization of nucleotides is believed to be a pathway for the replication of genetic material in the earliest cells. Adding template-directed polymerization changes the equilibrium structure of prelife if the rate constants meet certain criteria. In particular, if the basic reproductive ratio of sequences of a certain length exceeds one, then those sequences can attain high abundance. Furthermore, if many sequences replicate, then the longest sequences can reach high abundance even if the basic reproductive ratios of all sequences are less than one. We call this phenomenon "subcritical life." Subcritical life suggests that sequences long enough to be ribozymes can become abundant even if replication is relatively inefficient. Our work on the evolution of replication has interesting parallels to infection dynamics. Life (replication) can be seen as an infection of prelife. Finally, in Chapter 5, we study the emergence of complexity in early biochemical systems. RNA biochemistry is characterized by large differences in synthetic yield, reactivity to polymerization, and degradation rate, and these properties are believed to result in pools of highly homogeneous, low complexity sequences. Using simulations of prebiotic chemical systems, we show that template-directed ligation and the mass-action effect of sequence concatenation increase the average complexity and population diversity in pools of RNA molecules. We verify these theoretical results with experiments showing that ligation does enhance complexity in real RNA systems. We also find a correlation between predicted RNA folding energy and complexity, demonstrating the functional importance of this measure. These results contrast with previous assumptions that fine-tuning of the system is the only way to achieve high complexity. Our work shows that the chemical mechanisms involved in nucleic acid polymerization and oligomerization predispose the RNA world towards a diverse pool of complex, energetically stable sequences, setting the stage for the appearance of catalytic activity prior to the onset of natural selection. / by Michael L. Manapat. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2010. / Cataloged from PDF version of thesis. / Includes bibliographical references (p. 71-73). / This work focuses on a generalization of the models for rational homotopy theory developed by D. Sullivan and D. Quillen and p-adic homotopy developed by M. Mandell to K(1)-local homotopy theory. The work is divided into two parts. The first part is a reflection on M. Mandell's model for p-adic homotopy theory. Reformulating M. Mandell's result in terms of an adjunction between p-complete, nilpotent spaces of finite type and a subcategory of commutative HIF,-algebras, the main theorem shows that the unit of this adjunction induces an isomorphism between the unstable HF, Adams spectral sequence and the HIF, Goerss-Hopkins spectral sequence. The second part generalizes M. Mandell's model for p-adic homotopy theory to give a model for K(1)-localization. The main theorem gives a model for the K(1)- localization of an infinite loop space as a certain derived mapping space of K(1)- local ring spectra. This result is proven by analyzing a more general functor from finite spectra to a mapping space of K -algebras using homotopy calculus, and then taking the continuous homotopy fixed points with respect to the prime to p Adams operations. / Ph.D.

Thesis: Ph. D., Massachusetts Institute of Technology, Department of Mathematics, 2016. / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 121-127). / We revisit foundational questions in the kinetic theory of linkages and origami, investigating their folding/unfolding behaviors and the computational complexity thereof. In Chapter 2, we exactly settle the complexity of realizability, rigidity, and global rigidy for graphs and linkages in the plane, even when the graphs are (1) promised to avoid crossings in all configurations, or (2) equilateral and required to be drawn without crossings ("matchstick graphs"): these problems are complete for the class IR defined by the Existential Theory of the Reals, or its complement. To accomplish this, we prove a strong form of Kempe's Universality Theorem for linkages that avoid crossings. Chapter 3 turns to "self-touching" linkage configurations, whose bars are allowed to rest against each other without passing through. We propose an elegant model for representing such configurations using infinitesimal perturbations, working over a field R(e) that includes formal infinitesimals. Using this model and the powerful Tarski-Seidenberg "transfer" principle for real closed fields, we prove a self-touching version of the celebrated Expansive Carpenter's Rule Theorem. We switch to folding polyhedra in Chapter 4: we show a simple technique to continuously flatten the surface of any convex polyhedron without distorting intrinsic surface distances or letting the surface pierce itself. This origami motion is quite general, and applies to convex polytopes of any dimension. To prove that no piercing occurs, we apply the same infinitesimal techniques from Chapter 3 to formulate a new formal model of self-touching origami that is simpler to work with than existing models. Finally, Chapter 5 proves polyhedra are hard to edge unfold: it is NP-hard to decide whether a polyhedron may be cut along edges and unfolded into a non-overlapping net. This edge unfolding problem is not known to be solvable in NP due to precision issues, but we show this is not the only obstacle: it is NP complete for orthogonal polyhedra with integer coordinates (all of whose unfolding also have integer coordinates) / by Zachary Abel. / Ph. D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 1988. / Includes bibliographical references. / by Catherine Durso. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 1971. / Vita. / Bibliography: leaves 103-106. / by Stephen G. Simpson. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2013. / Cataloged from PDF version of thesis. / Includes bibliographical references (p. 263-272). / A secure multi-party computation (MPC) protocol for computing a function f allows a group of parties to jointly evaluate f over their private inputs, such that a computationally bounded adversary who corrupts a subset of the parties can not learn anything beyond the inputs of the corrupted parties and the output of the function f. General MPC completeness theorems in the 1980s showed that every efficiently computable function can be evaluated securely in this fashion [Yao86, GMW87, CCD87, BGW88] using the existence of cryptography. In the following decades, progress has been made toward making MPC protocols efficient enough to be deployed in real-world applications. However, recent technological developments have brought with them a slew of new challenges, from new security threats to a question of whether protocols can scale up with the demand of distributed computations on massive data. Before one can make effective use of MPC, these challenges must be addressed. In this thesis, we focus on two lines of research toward this goal: " Protocols resilient to side-channel attacks. We consider a strengthened adversarial model where, in addition to corrupting a subset of parties, the adversary may leak partial information on the secret states of honest parties during the protocol. In presence of such adversary, we first focus on preserving the correctness guarantees of MPC computations. We then proceed to address security guarantees, using cryptography. We provide two results: an MPC protocol whose security provably "degrades gracefully" with the amount of leakage information obtained by the adversary, and a second protocol which provides complete security assuming a (necessary) one-time preprocessing phase during which leakage cannot occur. * Protocols with scalable communication requirements. We devise MPC protocols with communication locality: namely, each party only needs to communicate with a small (polylog) number of dynamically chosen parties. Our techniques use digital signatures and extend particularly well to the case when the function f is a sublinear algorithm whose execution depends on o(n) of the n parties' inputs. / by Elette Chantae Boyle. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 1985. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND SCIENCE. / Bibliography: leaves 183-189. / by Janice H. Hammond. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2004. / Includes bibliographical references (p. 53-56). / There is a formula by the string theorists Dijkgraaf, Moore, Verlinde and Verlinde, expressing the orbifold elliptic genus of the symmetric powers of an almost complex manifold M in terms of the elliptic genus of M itself. We show that from the point of view of elliptic cohomology an analogous p-typical statement follows as an easy corollary from the fact that the map of spectra corresponding to the genus preserves power operations. We define higher chromatic versions of the notion of orbifold genus, involving h-tuples rather than pairs of commuting elements. Using homotopy theoretic methods we are able to prove an integrality result and show that our definition is independent of the representation of the orbifold. Our setup is so simple, that it allows us to prove DMVV-type product formulas for these higher chromatic orbifold genera in the same way that the product formula for the topological Todd genus is proved. More precisely, we show that any genus induced by an H[omega]-map into one of the Morava-Lubin-Tate cohomology theories Eh has such a product formula and that the formula depends only on h and not on the genus. Since the complex H[omega]-genera into Eh have been classified in [And95], a large family of genera to which our results apply is completely understood. Loosely speaking, our result says that some Borcherds lifts have a well-known homotopy theoretic refinement, namely total symmetric powers in elliptic cohomology. / by Nora Ganter. / Ph.D.