The dissertation consists of two parts. The first part is devoted to results in Discrepancy Theory. We consider geometric discrepancy in higher dimensions (d > 2) and obtain estimates in Exponential Orlicz Spaces. We establish a series of dichotomy-type results for the discrepancy function which state that if the L¹ norm of the discrepancy function is too small (smaller than the conjectural bound), then the discrepancy function has to be very large in some other function space.The second part of the thesis is devoted to results in Additive Combinatorics. For a set with small doubling an order-preserving Freiman 2-isomorphism is constructed which maps the set to a dense subset of an interval. We also present several applications.

We say that a covering space of the surface S over X has the Birman--Hilden property if the subgroup of the mapping class group of X consisting of mapping classes that have representatives that lift to S embeds in the mapping class group of S modulo the group of deck transformations. We identify one necessary condition and one sufficient condition for when a covering space has this property. We give new explicit examples of irregular branched covering spaces that do not satisfy the necessary condition as well as explicit covering spaces that satisfy the sufficient condition. Our criteria are conditions on simple closed curves, and our proofs use the combinatorial topology of curves on surfaces.

Phylogenetic analysis, or the inference of evolutionary history is done routinely by biologists and is one of the most important problems in systematic biology. In this thesis, we study two computational problems in the area. First, we study the evolutionary tree reconstruction problem under the character compatibility (CC) paradigm and give a polynomial time approximation scheme (PTAS) for a variation of the formulation called fractional character compatibility (FCC), which has been proven to be NP-hard. We also present a very simple algorithm called the Ordinal Split Method (OSM) to generate bipartitions given sequence data, which can be served as a front-end to the PTAS. The performance of the OSM and the validity of the FCC formulation are studied through simulation experiments. The second part of this thesis presents an efficient algorithm to compare evolutionary trees using the quartet metric. Different evolutionary hypothesis arises when different data sets are used or when different tree inference methods are applied to the same data set. Tree comparisons are routinely done by biologists to evaluate the quality of their tree inference experiments. The quartet metric has many desirable properties but its use has been hindered by its relatively heavy computational requirements. We address this problem by giving the first O(n^2) time algorithm to compute the quartet distance between two evolutionary trees.

Geometric packing problems are NP-complete problems that arise in VLSI design. In this thesis, we present two novel algorithms using dynamic programming to compute exactly the maximum number of k x k squares of unit size that can be packed without overlap into a given n x m grid. The first algorithm was implemented and ran successfully on problems of large input up to 1,000,000 nodes for different values. A heuristic based on the second algorithm is implemented. This heuristic is fast in practice, but may not always be giving optimal times in theory. However, over a wide range of random data this version of the algorithm is giving very good solutions very fast and runs on problems of up to 100,000,000 nodes in a grid and different ranges for the variables. It is also shown that this version of algorithm is clearly superior to the first algorithm and has shown to be very efficient in practice.

Heterogeneity in modern datacenters is on the rise, in hardware resource characteristics, in workload characteristics, and in dynamic characteristics (e.g., a memoryresident copy of input data). As a result, which machines are assigned to a given job can have a significant impact. For example, a job may run faster on the same machine as its input data or with a given hardware accelerator, while still being runnable on other machines, albeit less efficiently. Heterogeneity takes on more complex forms as sets of resources differ in the level of performance they deliver, even if they consist of identical individual units, such as with rack-level locality. We refer to this as combinatorial heterogeneity. Mixes of jobs with strict SLOs on completion time and increasingly available runtime estimates in production datacenters deepen the challenge of matching the right resources to the right workloads at the right time. In this dissertation, we hypothesize that it is possible and beneficial to simultaneously leverage all of this information in the form of declaratively specified spacetime soft constraints. To accomplish this, we first design and develop our principal building block—a novel Space-Time Request Language (STRL). It enables the expression of jobs’ preferences and flexibility in a general, extensible way by using a declarative, composable, intuitive algebraic expression structure. Second, building on the generality of STRL, we propose an equally general STRL Compiler that automatically compiles STRL expressions into Mixed Integer Linear Programming (MILP) problems that can be aggregated and solved to maximize the overall value of shared cluster resources. These theoretical contributions form the foundation for the system we architect, called TetriSched, that instantiates our conceptual contributions: (a) declarative soft constraints, (b) space-time soft constraints, (c) combinatorial constraints, (d) orderless global scheduling, and (e) in situ preemption. We also propose a set of mechanisms that extend the scope and the practicality of TetriSched’s deployment by analyzing and improving on its scalability, enabling and studying the efficacy of preemption, and featuring a set of runtime mis-estimation handling mechanisms to address runtime prediction inaccuracy. In collaboration with Microsoft, we adapt some of these ideas as we design and implement a heterogeneity-aware resource reservation system called Aramid with support for ordinal placement preferences targeting deployment in production clusters at Microsoft scale. A combination of simulation and real cluster experiments with synthetic and production-derived workloads, a range of workload intensities, degrees of burstiness, preference strengths, and input inaccuracies support our hypothesis that leveraging space-time soft constraints (a) significantly improves scheduling quality and (b) is possible to achieve in a practical deployment.

<p>This thesis focuses on the development of algorithms that will allow protein design calculations to incorporate more realistic modeling assumptions. Protein design algorithms search large sequence spaces for protein sequences that are biologically and medically useful. Better modeling could improve the chance of success in designs and expand the range of problems to which these algorithms are applied. I have developed algorithms to improve modeling of backbone flexibility (DEEPer) and of more extensive continuous flexibility in general (EPIC and LUTE). I’ve also developed algorithms to perform multistate designs, which account for effects like specificity, with provable guarantees of accuracy (COMETS), and to accommodate a wider range of energy functions in design (EPIC and LUTE).</p> / Dissertation

The game of Subset Take-Away is an impartial combinatorial game posed by David Gale in 1974. The game can be played on various discrete structures, including but not limited to graphs, hypergraphs, polygonal complexes, and partially ordered sets. While a universal winning strategy has yet to be found, results have been found in certain cases. In 2003 R. Riehemann focused on Subset Take-Away on bipartite graphs and produced a complete game analysis by studying nim-values. In this work, we extend the notion of Take-Away on a bipartite graph to Take-Away on particular hypergraphs, namely oddly-uniform hypergraphs and evenly-uniform hypergraphs whose vertices satisfy a particular coloring condition. On both structures we provide a complete game analysis via nim-values. From here, we consider different discrete structures and slight variations of the rules for Take-Away to produce some interesting results. Under certain conditions, polygonal complexes exhibit a sequence of nim-values which are unbounded but have a well-behaved pattern. Under other conditions, the nim-value of a polygonal complex is bounded and predictable based on information about the complex itself. We introduce a Take-Away variant which we call “Take-As-Much-As-You-Want”, and we show that, again, nim-values can grow without bound, but fortunately they are very easily described for a given graph based on the total number of vertices and edges of the graph. Finally we consider Take-Away on a specific type of partially ordered set which we call a rank-complete poset. We have results, again via an analysis of nim-values, for Take-Away on a rank-complete poset for both ordinary play as well as misère play.

In protein engineering, rational design and selection from combinatorial libraries are methods used to develop proteins with new or improved features. A very important protein for the biological sciences is the antibody that is used as a detecting agent in numerous laboratory assays. Antibodies used for these purposes are often ”man-made”, by immunising animals with the desired target, or by selections from combinatorial libraries. Naturally, antibodies are part of the immune defence protecting us from foreign attacks from e.g. bacteria or viruses. Some bacteria have evolved surface proteins that can bind to proteins abundant in the blood, like antibodies and serum albumin. By doing so, the bacteria can cover themselves in the host’s own proteins and through that evade being detected by the immune system. Two such proteins are Protein A from Staphylococcus aureus and Protein G from group C and G Streptococci. Both these proteins contain domains that bind to antibodies, one of which is denoted C2 (from Protein G) and another B (from Protein A). The B domain have been further engineered to the Z domain. In this thesis protein engineering has been used to develop variants of the C2 and Z domains for site-specific labelling of antibodies and for antibody purification with mild elution. By taking advantage of the domains’ inherent affinity for antibodies, engineering and design of certain amino acids or protein motifs of the domains have resulted in proteins with new properties. A photo crosslinking amino acid, p-benzoylphenylalanine, have been introduced at different positions to the C2 domain, rendering three new protein domains that can be used for site-specific labelling of antibodies at the Fc or Fab fragment. These domains were used for labelling antibodies with lanthanides and used for detection in a multiplex immunoassay. Moreover, a library of calcium-binding loops was grafted onto the Z domain and used for selection of a domain that binds antibodies in a calcium dependent manner. This engineered protein domain can be used for the purification of antibodies using milder elution conditions, by calcium removal, as compared to traditional antibody purification.

This dissertation is concerned with the existence and the isomorphism of designs. The first part studies the existence of designs. Chapter I shows how to obtain a design from a difference family. Chapters II to IV study the existence of an affine 3-(p^m,4,λ) design where the v-set is the Galois field GF(p^m). Associated to each prime p, this paper constructs a graph. If the graph has a 1-factor, then a difference family and hence an affine design exists. The question arises of how to determine when the graph has a 1-factor. It is not hard to see that the graph is connected and of even order. Tutte's theorem shows that if the graph is 2-connected and regular of degree three, then the graph has a 1-factor. By using the concept of quadratic reciprocity, this paper shows that if p Ξ 53 or 77 (mod 120), the graph is almost regular of degree three, i.e., every vertex has degree three, except two vertices each have degree tow. Adding an extra edge joining the two vertices with degree tow gives a regular graph of degree three. Also, Tutte proved that if A is an edge of the graph satisfying the above conditions, then it must have a 1-factor which contains A. The second part of the dissertation is concerned with determining if two designs are isomorphic. Here the v-set is any group G and translation by any element in G gives a design automorphism. Given a design B and its difference family D, two topological spaces, B and D, are constructed. We give topological conditions which imply that a design isomorphism is a group isomorphism.

Cette thèse est consacrée à l’étude de familles à un paramètre de coproduits sur lesfonctions symétriques et leurs analogues non commutatifs. On montre en introduisant une base appropriée qu’une famille à un paramètre d’algèbres de Hopf introduite par Foissy interpole entre l’algèbre de Faà di Bruno et l’algèbre de Farahat-Higman. Les constantes de structure dans cette base sont des déformations des constantes de structures de l’algèbre de Farahat-Higman dans la base des projections des classes de conjugaison. On obtient pour ces constantes de structure déformées un analogue des formules de Macdonald. Foissy a également introduit un analogue non commutatif de cette famille d’algèbres de Hopf, qui interpole entre l’algèbre de Hopf des fonctions symétriques non commutatives et l’algèbre de Faà di Bruno non commutative. Après avoir donné une nouvelle interprétation combinatoire de la formule de Brouder-Frabetti-Krattenthaler pour l’antipode de l’algèbre de Faà di Bruno non commutative, qui est une forme de la formule d’inversion de Lagrange non commutative, on donne une déformation à un paramètre de cette formule. Plus précisément, on obtient une formule explicite pour l’antipode de la déformation de Foissy dans sa version non commutative. On donne aussi d’autres propriétés combinatoires de l’algèbre de Faà di Bruno non commutative et d’autres résultats permettant d’étudier les deux familles d’algèbre de Hopf de Foissy. Ainsi, on généralise par exemple d’autres formes de la formule d’inversion de Lagrange non commutative en donnant d’autres formules qui calculent l’antipode de la deuxième déformation. / This thesis is devoted to study one-parameter families of coproducts on symmetric functionsand their noncommutative analogues. We show, by introducing an appropriate basis,that a one-parameter family of Hopf algebras introduced by Foissy interpolates between theFa`a di Bruno algebra and the Farahat-Higman algebra. The structure constants in this basisare deformations of the structure constants of the Farahat-Higman algebra in the basis ofprojections of conjugacy classes. For these deformed structure constants, we obtain an analogueof the Macdonald formulas.Foissy has also introduced a noncommutative analogue of this family of Hopf algebras. Itinterpolates between the Hopf algebra of noncommutative symmetric functions and the noncommutativeFa`a di Bruno algebra. First, we give a new combinatorial interpretation ofthe Brouder-Frabetti-Krattenthaler formula for the antipode of the noncommutative Fa`a diBruno algebra, that is a form of the noncommutative Lagrange inversion formula. Then, wegive a one-parameter deformation of this formula. Namely, it is an explicit formula for theantipode of the noncommutative family.We also give other combinatorial properties of the noncommutative Fa`a di Bruno algebra,and other results about the families of Hopf algebras of Foissy. In this way, we generalize otherforms of the noncommutative Lagrange inversion formula. Namely, we give other formulasfor the antipode of the noncommutative family.