The all terminal reliability of a graph G is the probability that at least a spanning tree is operational, given that vertices are always operational and edges independently operate with probability p in [0,1]. In this thesis, an investigation of all terminal reliability is undertaken. An open problem regarding the non-existence of optimal graphs is settled and analytic properties, such as roots, thresholds, inflection points, fixed points and the average value of the all terminal reliability polynomial on [0,1] are studied. A new reliability problem, the k -clique reliability for a graph G is introduced. The k-clique reliability is the probability that at least a clique of size k is operational, given that vertices operate independently with probability p in [0,1] . For k-clique reliability the existence of optimal networks, analytic properties, associated complexes and the roots are studied. Applications to problems regarding independence polynomials are developed as well.

In this thesis we describe how the balancing of the $\operatorname{Tor}$ functor can be used to compute the minimal free resolution of a graded module $M$ over the polynomial ring $B=\mathbb{K}[X_0,\dots,X_m]$ ($\mathbb{K}$ a field $X_i$'s indeterminates). Using a correspondence due to R. Stanley and M. Hochster, we explicitly show how this approach can be used in the case when $M=\mathbb{K}[S]$, the semigroup ring of a subsemigroup $S\subseteq \mathbb{N}^l$ (containing $0$) over $\mathbb{K}$ and when $M$ is a monomial ideal of $B$. We also study the class of affine semigroup rings for which $\mathbb{K}[S]\cong B/\mathfrak{p}$ is the homogeneous coordinate ring of a monomial curve in $\mathbb{P}^n_{\mathbb{K}}$. We use easily computable combinatorial and arithmetic properties of $S$ to define a notion which we call stabilization. We provide a direct proof showing how stabilization gives a bound on the $\mathbb{N}$-graded degree of minimal generators of $\mathfrak{p}$ and also show that it is related to the regularity of $\mathfrak{p}$. Moreover, we partition the above mentioned class into three cases and show that this partitioning is reflected in how the regularity is attained. An interesting consequence is that the regularity of $\mathfrak{p}$ can be effectively computed by elementary means. / Thesis (Master, Mathematics & Statistics) -- Queen's University, 2008-09-24 09:49:35.462

Motivated by the longest increasing subsequence problem, we examine sundry topics at the interface of enumerative/algebraic combinatorics and random matrix theory. We begin with an expository account of the increasing subsequence problem, contextualizing it as an ``exactly solvable'' Ramsey-type problem and introducing the RSK correspondence. New proofs and generalizations of some of the key results in increasing subsequence theory are given. These include Regev's single scaling limit, Gessel's Toeplitz determinant identity, and Rains' integral representation. The double scaling limit (Baik-Deift-Johansson theorem) is briefly described, although we have no new results in that direction. Following up on the appearance of determinantal generating functions in increasing subsequence type problems, we are led to a connection between combinatorics and the ensemble of truncated random unitary matrices, which we describe in terms of Fisher's random-turns vicious walker model from statistical mechanics. We prove that the moment generating function of the trace of a truncated random unitary matrix is the grand canonical partition function for Fisher's random-turns model with reunions. Finally, we consider unitary matrix integrals of a very general type, namely the ``correlation functions'' of entries of Haar-distributed random matrices. We show that these expand perturbatively as generating functions for class multiplicities in symmetric functions of Jucys-Murphy elements, thus addressing a problem originally raised by De Wit and t'Hooft and recently resurrected by Collins. We argue that this expansion is the CUE counterpart of genus expansion. / Thesis (Ph.D, Mathematics & Statistics) -- Queen's University, 2009-09-27 12:27:21.479

The central result presented in this thesis is van der Waerden's theorem on arithmetic progressions. Van der Waerden's theorem guarantees that for any integers k and r, there is an n so that however the set {1, 2, ... , n} is split into r disjoint partition classes, at least one partition class will contain a k-term arithmetic progression. Presented here are a number of variations and generalizations of van der Waerden's theorem that utilize a wide range of techniques from areas of mathematics including combinatorics, number theory, algebra, and topology.

This is an expository thesis. In this thesis we study out-orientations of hypergraphs, where every hyperarc has one tail vertex. We study hypergraphs that admit out-orientations covering supermodular-type connectivity requirements. For this, we follow a paper of Frank. We also study the Steiner rooted orientation problem. Given a hypergraph and a subset of vertices S ⊆ V, the goal is to give necessary and sufficient conditions for an orientation such that the connectivity between a root vertex and each vertex of S is at least k, for a positive integer k. We follow a paper by Kiraly and Lau, where they prove that every 2k-hyperedge connected hypergraph has such an orientation.

This thesis concerns the analysis of the unconditional security of quantum cryptographic protocols using convex optimization techniques. It is divided into the study of coin-flipping and oblivious transfer. We first examine a family of coin-flipping protocols. Almost all of the handful of explicitly described coin-flipping protocols are based on bit-commitment. To explore the possibility of finding explicit optimal or near-optimal protocols, we focus on a class which generalizes such protocols. We call these $\BCCF$-protocols, for bit-commitment based coin-flipping. We use the semidefinite programming (SDP) formulation of cheating strategies along the lines of Kitaev to analyze the structure of the protocols. In the first part of the thesis, we show how these semidefinite programs can be used to simplify the analysis of the protocol. In particular, we show that a particular set of cheating strategies contains an optimal strategy. This reduces the problem to optimizing a linear combination of fidelity functions over a polytope which has several benefits. First, it allows one to model cheating probabilities using a simpler class of optimization problems known as second-order cone programs (SOCPs). Second, it helps with the construction of point games due to Kitaev as described in Mochon's work. Point games were developed to give a new perspective for studying quantum protocols. In some sense, the notion of point games is dual to the notion of protocols. There has been increased research activity in optimization concerning generalizing theory and algorithms for linear programming to much wider classes of optimization problems such as semidefinite programming. For example, semidefinite programming provides a tool for potentially improving results based on linear programming or investigating old problems that have eluded analysis by linear programming. In this sense, the history of semidefinite programming is very similar to the history of quantum computation. Quantum computing gives a generalized model of computation to tackle new and old problems, improving on and generalizing older classical techniques. Indeed, there are striking differences between linear programming and semidefinite programming as there are between classical and quantum computation. In this thesis, we strengthen this analogy by studying a family of classical coin-flipping protocols based on classical bit-commitment. Cheating strategies for these ``classical $\BCCF$-protocols'' can be formulated as linear programs (LPs) which are closely related to the semidefinite programs for the quantum version. In fact, we can construct point games for the classical protocols as well using the analysis for the quantum case. Using point games, we prove that every classical $\BCCF$-protocol allows exactly one of the parties to entirely determine the outcome. Also, we rederive Kitaev's lower bound to show that only ``classical'' protocols can saturate Kitaev's analysis. Moreover, if the product of Alice and Bob's optimal cheating probabilities is $1/2$, then at least one party can cheat with probability $1$. The second part concerns the design of an algorithm to search for $\BCCF$-protocols with small bias. Most coin-flipping protocols with more than three rounds have eluded direct analysis. To better understand the properties of optimal $\BCCF$-protocols with four or more rounds, we turn to computational experiments. We design a computational optimization approach to search for the best protocol based on the semidefinite programming formulations of cheating strategies. We create a protocol filter using cheating strategies, some of which build upon known strategies and others are based on convex optimization and linear algebra. The protocol filter efficiently eliminates candidate protocols with too high a bias. Using this protocol filter and symmetry arguments, we perform searches in a matter of days that would have otherwise taken millions of years. Our experiments checked $10^{16}$ four and six-round $\BCCF$-protocols and suggest that the optimal bias is $1/4$. The third part examines the relationship between oblivious transfer, bit-commitment, and coin-flipping. We consider oblivious transfer which succeeds with probability $1$ when the two parties are honest and construct a simple protocol with security provably better than any classical protocol. We also derive a lower bound by constructing a bit-commitment protocol from an oblivious transfer protocol. Known lower bounds for bit-commitment then lead to a constant lower bound on the bias of oblivious transfer. Finally, we show that it is possible to use Kitaev's semidefinite programming formulation of cheating strategies to obtain optimal lower bounds on a ``forcing'' variant of oblivious transfer related to coin-flipping.

Pairing-based cryptography has been employed to obtain several advantageous cryptographic protocols. In particular, there exist several identity-based variants of common cryptographic schemes. The computation of a single pairing is a comparatively expensive operation, since it often requires many operations in the underlying elliptic curve. In this thesis, we explore the efficient computation of pairings. Computation of the Tate pairing is done in two steps. First, a Miller function is computed, followed by the final exponentiation. We discuss the state-of-the-art optimizations for Miller function computation under various conditions. We are able to shave off a fixed number of operations in the final exponentiation. We consider methods to effectively parallelize the computation of pairings in a multi-core setting and discover that the Weil pairing may provide some advantage under certain conditions. This work is extended to the 192-bit security level and some unlikely candidate curves for such a setting are discovered. Electronic Toll Pricing (ETP) aims to improve road tolling by collecting toll fares electronically and without the need to slow down vehicles. In most ETP schemes, drivers are charged periodically based on the locations, times, distances or durations travelled. Many ETP schemes are currently deployed and although these systems are efficient, they require a great deal of knowledge regarding driving habits in order to operate correctly. We present an ETP scheme where pairing-based BLS signatures play an important role. Finally, we discuss the security of pairings in the presence of an efficient algorithm to invert the pairing. We generalize previous results to the setting of asymmetric pairings as well as give a simplified proof in the symmetric setting.

The central result presented in this thesis is van der Waerden's theorem on arithmetic progressions. Van der Waerden's theorem guarantees that for any integers k and r, there is an n so that however the set {1, 2, ... , n} is split into r disjoint partition classes, at least one partition class will contain a k-term arithmetic progression. Presented here are a number of variations and generalizations of van der Waerden's theorem that utilize a wide range of techniques from areas of mathematics including combinatorics, number theory, algebra, and topology.

This thesis consists of the manuscripts of two research papers. In the first paper, we verify a recent conjecture of Kenyon/Szendroi by computing the generating function for pyramid partitions. Pyramid partitions are closely related to Aztec Diamonds; their generating function turns out to be the partition function for the Donaldson-Thomas theory of a non-commutative resolution of the conifold singularity {x₁‚x₂‚‚ - x₃‚ƒx₄‚„ = 0}⊂ C⁴. The proof does not require algebraic geometry; it uses a modified version of the domino (or dimer) shuffling algorithm of Elkies, Kuperberg, Larsen and Propp. In the second paper, we derive two multivariate generating functions for three-dimensional Young diagrams (also called plane partitions). The variables correspond to a colouring of the boxes according to a finite abelian subgroup G of SO(3). These generating functions turn out to be orbifold Donaldson-Thomas partition functions for the orbifold [C³/G]. We need only the vertex operator methods of Okounkov-Reshetikhin-Vafa for the easy case G = Zn; to handle the considerably more difficult case G = Z₂‚‚ x Z₂‚‚, we will also use a refinement of the author's recent q-enumeration of pyramid partitions. In the appendix, written by Jim Bryan, we relate the diagram generating functions to the Donaldson-Thomas partition functions of the orbifold [C³/G]. We find a relationship between the Donaldson-Thomas partition functions of the orbifold and its G-Hilbert scheme resolution. We formulate a crepant resolution conjecture for the Donaldson-Thomas theory of local orbifolds satisfying the Hard Lefschetz condition.

Randomised algorithms are an effective method of attacking computationally intractable problems. A simple and fast randomised algorithm may produce results to an accuracy sufficient for many purposes, especially in the average case. In this thesis we consider average case analyses of heuristics for certain NP-hard graph optimisation problems. In particular, we consider algorithms that find dominating sets of random regular directed graphs. As well as providing an average case analysis, our results also determine new upper bounds on domination numbers of random regular directed graphs. The algorithms for random regular directed graphs considered in this thesis are known as prioritised algorithms. Each prioritised algorithm determines a discrete random process. This discrete process may be continuously approximated using differential equations. Under certain conditions, the solutions to these differential equations describe the behaviour of the prioritised algorithm. Applying such an analysis to prioritised algorithms directly is difficult. However, we are able to use prioritised algorithms to define new algorithms, called deprioritised algorithms, that can be analysed in this fashion. Defining a deprioritised algorithm based on a given prioritised algorithm, and then analysing the deprioritised algorithm, is called the deprioritised approach. The initial theory describing the deprioritised approach was developed by Wormald and has been successfully applied in many cases. However not all algorithms are covered by Wormald??s theory: for example, algorithms for random regular directed graphs. The main contribution of this thesis is the extension of the deprioritised approach to a larger class of prioritised algorithms. We demonstrate the new theory by applying it to two algorithms which find dominating sets of random regular directed graphs.