Browsing Combinatorics and Optimization by Subject "Mathematics"
Now showing items 1-20 of 50
-
Algebraic Analysis of Vertex-Distinguishing Edge-Colorings
(University of Waterloo, 2006)Vertex-distinguishing edge-colorings (vdec colorings) are a restriction of proper edge-colorings. These special colorings require that the sets of edge colors incident to every vertex be distinct. This is a relatively ... -
Algebraic Tori in Cryptography
(University of Waterloo, 2005)Communicating bits over a network is expensive. Therefore, cryptosystems that transmit as little data as possible are valuable. This thesis studies several cryptosystems that require significantly less bandwidth than ... -
Applications of Bilinear Maps in Cryptography
(University of Waterloo, 2002)It was recently discovered by Joux [30] and Sakai, Ohgishi and Kasahara [47] that bilinear maps could be used to construct cryptographic schemes. Since then, bilinear maps have been used in applications as varied as ... -
Approximate Private Quantum Channels
(University of Waterloo, 2006)This thesis includes a survey of the results known for private and approximate private quantum channels. We develop the best known upper bound for ε-randomizing maps, <em>n</em> + 2log(1/ε) + <em>c</em> ... -
Character Polynomials and Lagrange Inversion
(University of Waterloo, 2005)In this thesis, we investigate two expressions for symmetric group characters: Kerov?s universal character polynomials and Stanley?s character polynomials. We give a new explicit form for Kerov?s polynomials, which ... -
Colouring Cayley Graphs
(University of Waterloo, 2005)We will discuss three ways to bound the chromatic number on a Cayley graph. 1. If the connection set contains information about a smaller graph, then these two graphs are related. Using this information, we will ... -
Colouring Subspaces
(University of Waterloo, 2005)This thesis was originally motivated by considering vector space analogues of problems in extremal set theory, but our main results concern colouring a graph that is intimately related to these vector space analogues. ... -
Combinatorial Arithmetic on Elliptic Curves
(University of Waterloo, 2017-09-27)We propose a scalar multiplication technique on an elliptic curve, which operates on triples of collinear points. The computation of this operation requires a new approach to operation chains, with similarities to Montgomery ... -
Combinatorial Constructions for Transitive Factorizations in the Symmetric Group
(University of Waterloo, 2004)We consider the problem of counting <i>transitive factorizations</i> of permutations; that is, we study tuples (σ<i>r</i>,. . . ,σ1) of permutations on {1,. . . ,<i>n</i>} such that (1) the product ... -
Continuous-time Quantum Algorithms: Searching and Adiabatic Computation
(University of Waterloo, 2002)One of the most important quantum algorithms is Grover's search algorithm [G96]. Quantum searching can be used to speed up the search for solutions to NP-complete problems e. g. 3SAT. Even so, the best known quantum ... -
Convergence Analysis of Generalized Primal-Dual Interior-Point Algorithms for Linear Optimization
(University of Waterloo, 2002)We study the zeroth-, first-, and second-order algorithms proposed by Tuncel. The zeroth-order algorithms are the generalization of the classic primal-dual affine-scaling methods, and have a strong connection with the ... -
Counting Bases
(University of Waterloo, 2004)A theorem of Edmonds characterizes when a pair of matroids has a common basis. Enumerating the common bases of a pair of matroid is a much harder problem, and includes the #P-complete problem of counting the number of ... -
The Cycle Spaces of an Infinite Graph
(University of Waterloo, 2006)The edge space of a finite graph <em>G</em> = (<em>V</em>, <em>E</em>) over a field F is simply an assignment of field elements to the edges of the graph. The edge space can equally be thought of us an |<em>E</em>|-dimensional ... -
Design and Analysis of RC4-like Stream Ciphers
(University of Waterloo, 2005)RC4 is one of the most widely used ciphers in practical software applications. In this thesis we examine security and design aspects of RC4. First we describe the functioning of RC4 and present previously published ... -
Differential Equations and Depth First Search for Enumeration of Maps in Surfaces
(University of Waterloo, 1999)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, ... -
Digital Rights Management and Code Obfuscation
(University of Waterloo, 2004)Digital Rights Management (DRM) involves retaining control over digital information, even after it has been made public. Preventing illegal file sharing on the Internet, which is a topic that has recently received a large ... -
Digital Signature Scheme Variations
(University of Waterloo, 2002)A digital signature scheme is the process of signing an electronic message that can be transmitted over a computer network. Digital signatures provide message authentication that can be proved to a third party. With ... -
Digital Signcryption
(University of Waterloo, 2005)Signcryption is a new cryptographic primitive which simultaneously provides both confidentiality and authenticity. Previously, these two goals had been considered separately, with encryption schemes providing confidentiality ... -
Efficient Integer Representations for Cryptographic Operations
(University of Waterloo, 2004)Every positive integer has a unique radix 2 representation which uses the digits {0,1}. However, if we allow digits other than 0 and 1, say {0,1,-1}, then a positive integer has many representations. Of these ... -
The Existence of Balanced Tournament Designs and Partitioned Balanced Tournament Designs
(University of Waterloo, 2001)A balanced tournament design of order <I>n</I>, BTD(<I>n</I>), defined on a 2<I>n</I>-set<I> V</i>, is an arrangement of the all of the (2<I>n</i>2) distinct unordered pairs of elements of <I>V</I> into an <I>n</I> X ...