Browsing Combinatorics and Optimization by Title
Now showing items 124-143 of 436
-
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 Signature Schemes Based on Hash Functions
(University of Waterloo, 2017-04-19)Cryptographers and security experts around the world have been awakened to the reality that one day (potentially soon) large-scale quantum computers may be available. Most of the public-key cryptosystems employed today on ... -
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 ... -
Digraphs with All Induced Directed Cycles of the Same Length are not → χ -Bounded
(2022-10-07)For t > 2, let us call a digraph D t-chordal if all induced directed cycles in D have length equal to t. In an earlier paper, we asked for which t it is true that t-chordal graphs with bounded clique number have bounded ... -
Disasters in Abstracting Combinatorial Properties of Linear Dependence
(University of Waterloo, 2020-05-15)A notion of geometric structure can be given to a set of points without using a coordinate system by instead describing geometric relations between finite combinations of elements. The fundamental problem is to then ... -
Discrete Logarithm Cryptography
(University of Waterloo, 2010-04-27)The security of many cryptographic schemes relies on the intractability of the discrete logarithm problem (DLP) in groups. The most commonly used groups to deploy such schemes are the multiplicative (sub)groups of finite ... -
Discrete Quantum Walks on Graphs and Digraphs
(University of Waterloo, 2018-09-26)This thesis studies various models of discrete quantum walks on graphs and digraphs via a spectral approach. A discrete quantum walk on a digraph $X$ is determined by a unitary matrix $U$, which acts on complex functions ... -
Disproportionate Division
(Wiley, 2020-10-01)We study the disproportionate version of the classical cake-cutting problem: how efficiently can we divide a cake, here [0,1], among n ≥ 2 agents with different demands α1, α2,..., αn summing to 1? When all the agents have ... -
Distance-Biregular Graphs and Orthogonal Polynomials
(University of Waterloo, 2023-09-15)This thesis is about distance-biregular graphs– when they exist, what algebraic and structural properties they have, and how they arise in extremal problems. We develop a set of necessary conditions for a distance-biregular ... -
Dominating sets in Kneser graphs
(University of Waterloo, 2007-08-29)This thesis investigates dominating sets in Kneser graphs as well as a selection of other topics related to graph domination. Dominating sets in Kneser graphs, especially those of minimum size, often correspond to interesting ... -
Dynamic Pricing Schemes in Combinatorial Markets
(University of Waterloo, 2023-05-01)In combinatorial markets where buyers are self-interested, the buyers may make purchases that lead to suboptimal item allocations. As a central coordinator, our goal is to impose prices on the items of the market so that ... -
Dynamic Programming: Salesman to Surgeon
(University of Waterloo, 2013-05-15)Dynamic Programming is an optimization technique used in computer science and mathematics. Introduced in the 1950s, it has been applied to many classic combinatorial optimization problems, such as the Shortest Path Problem, ... -
Edge coloring multigraphs without small dense subsets
(Elsevier, 2015-12-06)One consequence of a long-standing conjecture of Goldberg and Seymour about the chromatic index of multigraphs would be the following statement. Suppose $G$ is a multigraph with maximum degree $\Delta$, such that no vertex ... -
Edge State Transfer
(University of Waterloo, 2019-01-11)Let G be a graph and let t be a positive real number. Then the evolution of the continuous quantum walk defined on G is described by the transition matrix U(t)=exp(itH).The matrix H is called Hamiltonian. So far the most ... -
Edge-disjoint Linkages in Infinite Graphs
(University of Waterloo, 2022-09-26)The main subject of this thesis is the infinite graph version of the weak linkage conjecture by Thomassen [24]. We first prove results about the structure of the lifting graph; Theorems 2.2.8, 2.2.24, and 2.3.1. As an ... -
The Edmonds-Giles Conjecture and its Relaxations
(University of Waterloo, 2022-12-23)Given a directed graph, a directed cut is a cut with all arcs oriented in the same direction, and a directed join is a set of arcs which intersects every directed cut at least once. Edmonds and Giles conjectured for all ... -
Efficient Composition of Discrete Time Quantum Walks
(University of Waterloo, 2017-01-20)It is well known that certain search problems are efficiently solved by quantum walk algorithms. Of particular interest are those problems whose efficient solutions involve nesting of search algorithms. The nesting of ... -
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 ... -
Efficient Jacobian Determination by Structure-Revealing Automatic Differentiation
(University of Waterloo, 2014-01-23)This thesis is concerned with the efficient computation of Jacobian matrices of nonlinear vector maps using automatic differentiation (AD). Specifically, we propose the use of two directed edge separator methods, the ... -
Efficient Pairings on Various Platforms
(University of Waterloo, 2012-05-14)Pairings have found a range of applications in many areas of cryptography. As such, to utilize the enormous potential of pairing-based protocols one needs to efficiently compute pairings across various computing platforms. ...