This thesis develops an algorithm for the Schubert calculus of the Grassmanian. Specifically, we state a puzzle-based, synthesis algorithm for a triple intersection of Schubert varieties. Our algorithm is a reformulation of the synthesis algorithm by Bercovici, Collins, Dykema, Li, and Timotin. We replace their combinatorial approach, based on specialized Lebesgue measures, with an approach based on the puzzles of Knutson, Tao and Woodward. The use of puzzles in our algorithm is beneficial for several reasons, foremost among them being the larger body of work exploiting puzzles. To understand the algorithm, we study the necessary Schubert calculus of the Grassmanian to define synthesis. We also discuss the puzzle-based Littlewood-Richardson rule, which connects puzzles to triple intersections of Schubert varieties. We also survey three combinatorial objects related to puzzles in which we include a puzzle-based construction, by King, Tollu, and Toumazet, of the well known Horn inequalities.

In 1912 Axel Thue sparked the study of combinatorics on words when he showed that the Thue-Morse sequence contains no overlaps, that is, factors of the form ayaya. Since then many interesting properties of sequences began to be discovered and studied. In this thesis, we consider a class of infinite sequences generated by automata, called the k-automatic sequences. In particular, we present a logical theory in which many properties of k-automatic sequences can be expressed as predicates and we show that such predicates are decidable. Our main contribution is the implementation of a theorem prover capable of practically characterizing many commonly sought-after properties of k-automatic sequences. We showcase a panoply of results achieved using our method. We give new explicit descriptions of the recurrence and appearance functions of a list of well-known k-automatic sequences. We define a related function, called the condensation function, and give explicit descriptions for it as well. We re-affirm known results on the critical exponent of some sequences and determine it for others where it was previously unknown. On the more theoretical side, we show that the subword complexity p(n) of k-automatic sequences is k-synchronized, i.e., the language of pairs (n, p(n)) (expressed in base k) is accepted by an automaton. Furthermore, we prove that the Lyndon factorization of k-automatic sequences is also k-automatic and explicitly compute the factorization for several sequences. Finally, we show that while the number of unbordered factors of length n is not k-synchronized, it is k-regular.

This thesis puts forward the conjecture that for <i>n</i> > 3<i>k</i> with <i>k</i> > 2, the generalized Petersen graph, <i>GP</i>(<i>n,k</i>) is Hamilton-laceable if <i>n</i> is even and <i>k</i> is odd, and it is Hamilton-connected otherwise. We take the first step in the proof of this conjecture by proving the case <i>n</i> = 3<i>k</i> + 1 and <i>k</i> greater than or equal to 1. We do this mainly by means of an induction which takes us from <i>GP</i>(3<i>k</i> + 1, <i>k</i>) to <i>GP</i>(3(<i>k</i> + 2) + 1, <i>k</i> + 2). The induction takes the form of mapping a Hamilton path in the smaller graph piecewise to the larger graph an inserting subpaths we call <i>rotors</i> to obtain a Hamilton path in the larger graph.

A map is an embedding of the vertices and edges of a graph into a compact 2-manifold such that the remainder of the surface has components homeomorphic to open disks. With the goal of proving the Four Colour Theorem, Tutte began the field of map enumeration in the 1960's. His methods included developing the edge deletion decomposition, developing and solving a recurrence and functional equation based on this decomposition, and developing the medial bijection between two equinumerous infinite families of maps. Beginning in the 1980's Jackson, Goulden and Visentin applied algebraic methods in enumeration of non-planar and non-orientable maps, to obtain results of interest for mathematical physics and algebraic geometry, and the Quadrangulation Conjecture and the Map-Jack Conjecture. A special case of the former is solved by Tutte's medial bijection. The latter uses Jack symmetric functions which are a topic of active research. In the 1960's Walsh and Lehman introduced a method of encoding orientable maps. We develop a similar method, based on depth first search and extended to non-orientable maps. With this, we develop a bijection that extends Tutte's medial bijection and partially solves the Quadrangulation Conjecture. Walsh extended Tutte's recurrence for planar maps to a recurrence for all orientable maps. We further extend the recurrence to include non-orientable maps, and express it as a partial differential equation satisfied by the generating series. By appropriately interpolating the differential equation and applying the depth first search method, we construct a parameter that empirically fulfils the conditions of the Map-Jack Conjecture, and we prove some of its predicted properties. Arques and Beraud recently obtained a continued fraction form of a specialisation of the generating series for maps. We apply the depth search method with an ordinary differential equation, to construct a bijection whose existence is implied by the continued fraction.

This thesis will address several problems in discrete optimization. These problems are considered hard to solve. However, good approximation algorithms for these problems may be helpful in approximating problems in computational biology and computer science. Given an undirected graph G=(V,E) and a family of subsets of vertices S, the minimum crossing spanning tree is a spanning tree where the maximum number of edges crossing any single set in S is minimized, where an edge crosses a set if it has exactly one endpoint in the set. This thesis will present two algorithms for special cases of minimum crossing spanning trees. The first algorithm is for the case where the sets of S are pairwise disjoint. It gives a spanning tree with the maximum crossing of a set being 2OPT+2, where OPT is the maximum crossing for a minimum crossing spanning tree. The second algorithm is for the case where the sets of S form a laminar family. Let b_i be a bound for each S_i in S. If there exists a spanning tree where each set S_i is crossed at most b_i times, the algorithm finds a spanning tree where each set S_i is crossed O(b_i log n) times. From this algorithm, one can get a spanning tree with maximum crossing O(OPT log n). Given an undirected graph G=(V,E), and a family of subsets of vertices S, the minimum crossing perfect matching is a perfect matching where the maximum number of edges crossing any set in S is minimized. A proof will be presented showing that finding a minimum crossing perfect matching is NP-hard, even when the graph is bipartite and the sets of S are pairwise disjoint.

Bilinear pairings on elliptic curves have many cryptographic applications such as identity based encryption, one-round three-party key agreement protocols, and short signature schemes. The elliptic curves which are suitable for pairing-based cryptography are called pairing friendly curves. The prime-order pairing friendly curves with embedding degrees k=3,4 and 6 were characterized by Miyaji, Nakabayashi and Takano. We study this characterization of MNT curves in details. We present explicit algorithms to obtain suitable curve parameters and to construct the corresponding elliptic curves. We also give a heuristic lower bound for the expected number of isogeny classes of MNT curves. Moreover, the related theoretical findings are compared with our experimental results.

In this thesis we consider some network design games that arise from common network design problems. A network design game involves multiple players who control nodes in a network, each of which has a personal interest in seeing their nodes connected in some manner. To this end, the players will submit bids to a mechanism whose task will be to select which of the players to connect, how to connect their nodes, and how much to charge each player for the connection. We rely on many fundamental results from mechanism design (from [8], [9] & [5]) in this thesis and focus our efforts on designing and analyzing cost-sharing methods. That is, for a given set of players and their connection requirements, our algorithms compute a solution that satisfies all the players’ requirements and calculates ’fair’ prices to charge each of them for the connection. Our cost-sharing methods use a primal-dual framework developed by Agrawal, Klein and Ravi in [1] and generalized by Goemans &Williamson in [3]. We modify the algorithms by using the concept of death-time introduced by K¨onemann, Leonardi & Sch¨afer in [6]. Our main result is a 2-budget balanced and cross-monotonic cost sharing method for the downwards monotone set cover game, which arises naturally from any downwards monotone 0, 1-function. We have also designed a 2-budget balanced and cross-monotonic cost sharing method for two versions of the edge cover game arising from the edge cover problem. These games are special cases of the downwards monotone set cover game. By a result by Immorlica, Mahdian & Mirrokni in [4] our result is best possible for the edge cover game. We also designed a cross-monotonic cost sharing method for a network design game we call the Even Parity Connection game arising from the T-Join problem that generalizes proper cut requirement functions. We can show our algorithm returns cost shares that recover at least half the cost of the solution. We conjecture that our cost sharing method for the even parity connection game is competitive and thus 2-budget balance.

Key establishment is the process whereby two or more parties derive a shared secret, typically used for subsequent confidential communication. However, identifying the exact security requirements for key establishment protocols is a non-trivial task. This thesis compares, extends and merges existing security definitions and models for key establishment protocols. The primary focus is on two-party key agreement schemes in the public-key setting. On one hand new protocols are proposed and analyzed in the existing Canetti-Krawzcyk model. On the other hand the thesis develops a security model and novel definition that capture the essential security attributes of the standardized Unified Model key agreement protocol. These analyses lead to the development of a new security model and related definitions that combine and extend the Canetti-Krawzcyk pre- and post- specified peer models in terms of provided security assurances. The thesis also provides a complete analysis of a one-pass key establishment scheme. There are security goals that no one-pass key establishment scheme can achieve, and hence the two-pass security models and definitions need to be adapted for one-pass protocols. The analysis provided here includes the description of the required modification to the underlying security model. Finally, a complete security argument meeting these altered conditions is presented as evidence supporting the security of the one-pass scheme. Lastly, validation and reusing short lived key pairs are related to efficiency, which is a major objective in practice. The thesis considers the formal implication of omitting validation steps and reusing short lived key pairs. The conclusions reached support the generally accepted cryptographic conventions that incoming messages should not be blindly trusted and extra care should be taken when key pairs are reused.

We propose a formal model for non-interactive message authentication protocols (NIMAPs) using two channels and analyze all the attacks that can occur in this model. Further, we introduce the notion of hybrid-collision resistant (HCR) hash functions. This leads to a new proposal for a NIMAP based on HCR hash functions. This protocol is as efficient as the best previous NIMAP while having a very simple structure and not requiring any long strings to be authenticated ahead of time. We investigate interactive message authentication protocols (IMAPs) and propose a new IMAP, based on the existence of interactive-collision resistant (ICR) hash functions, a new notion of hash function security. The efficient and easy-to-use structure of our IMAP makes it very practical in real world ad hoc network scenarios. We also look at message recognition protocols (MRPs) and prove that there is a one-to-one correspondence between non-interactive MRPs and digital signature schemes with message recovery. Further, we look at an existing recognition protocol and point out its inability to recover in case of a specific adversarial disruption. We improve this protocol by suggesting a variant which is equipped with a resynchronization process. Moreover, another variant of the protocol is proposed which self-recovers in case of an intrusion. Finally, we propose a new design for message recognition in ad hoc networks which does not make use of hash chains. This new design uses random passwords that are being refreshed in each session, as opposed to precomputed elements of a hash chain.

The main goal of cryptography is to enable secure communication over a public channel; often a secret shared among the communicating parties is used to achieve this. The process by which these parties agree on such a shared secret is called key agreement. In this thesis, we focus on two-party key agreement protocols in the public-key setting and study the various methods used to establish and validate public keys. We pay particular attention to certificateless key agreement schemes and attempt to formalize a relevant notion of security. To that end, we give a possible extension of the existing extended Canetti-Krawzcyk security model applicable to the certificateless setting. We observe that none of the certificateless protocols we have seen in the literature are secure in this model; it is an open question whether such schemes exist. We analyze several published certificateless key agreement protocols, demonstrating the existence of key compromise impersonation attacks and even a man-in-the-middle attack in one case, contrary to the claims of the authors. We also briefly describe weaknesses exhibited by these protocols in the context of our suggested security model.