Browsing Combinatorics and Optimization by Title
Now showing items 286-305 of 435
-
On The Density of Binary Matroids Without a Given Minor
(University of Waterloo, 2016-12-21)This thesis is motivated by the following question: how many elements can a simple binary matroid with no $\PG(t,2)$-minor have? This is a natural analogue of questions asked about the density of graphs in minor-closed ... -
On the effectiveness of isogeny walks for extending cover attacks on elliptic curves
(University of Waterloo, 2016-08-23)Cryptographic systems based on the elliptic curve discrete logarithm problem (ECDLP) are widely deployed in the world today. In order for such a system to guarantee a particular security level, the elliptic curve selected ... -
On the Efficiency and Security of Cryptographic Pairings
(University of Waterloo, 2012-12-19)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 ... -
On the Evolutionary Design of Quantum Circuits
(University of Waterloo, 2005)The goal of this work is to understand the application of the evolutionary programming approach to the problem of quantum circuit design. This problem is motivated by the following observations: <ul> <li>In order to ... -
On the Excluded Minors for Dyadic Matroids
(University of Waterloo, 2019-01-17)The study of the class of dyadic matroids, the matroids representable over both $GF(3)$ and $GF(5)$, is a natural step to finding the excluded minors for $GF(5)$-representability. In this thesis we characterize the ternary ... -
On the Integrality Gap of Directed Steiner Tree Problem
(University of Waterloo, 2014-05-27)In the Directed Steiner Tree problem, we are given a directed graph G = (V,E) with edge costs, a root vertex r ∈ V, and a terminal set X ⊆ V . The goal is to find the cheapest subset of edges that contains an r-t path for ... -
On the orientation of hypergraphs
(University of Waterloo, 2011-01-13)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 ... -
On the Polyhedral Lift-and-Project Rank Conjecture for the Fractional Stable Set Polytope
(University of Waterloo, 2008-01-16)In this thesis, we study the behaviour of Lovasz and Schrijver's lift-and-project operators N and N_0 while being applied recursively to the fractional stable set polytope of a graph. We focus on two related conjectures ... -
On the Power and Limitations of Shallow Quantum Circuits
(University of Waterloo, 2022-09-01)Constant-depth quantum circuits, or shallow quantum circuits, have been shown to exhibit behavior that is uniquely quantum. This thesis explores the power and limitations of constant-depth quantum circuits, in particular ... -
On the Relationship between Conjugate Gradient and Optimal First-Order Methods for Convex Optimization
(University of Waterloo, 2014-01-23)In a series of work initiated by Nemirovsky and Yudin, and later extended by Nesterov, first-order algorithms for unconstrained minimization with optimal theoretical complexity bound have been proposed. On the other hand, ... -
On the Role of Partition Inequalities in Classical Algorithms for Steiner Problems in Graphs
(University of Waterloo, 2006)The Steiner tree problem is a classical, well-studied, $\mathcal{NP}$-hard optimization problem. Here we are given an undirected graph $G=(V,E)$, a subset $R$ of $V$ of terminals, and non-negative costs $c_e$ for all ... -
On the Security of Leakage Resilient Public Key Cryptography
(University of Waterloo, 2012-04-30)Side channel attacks, where an attacker learns some physical information about the state of a device, are one of the ways in which cryptographic schemes are broken in practice. "Provably secure" schemes are subject to these ... -
On the Strongly Connected Components of Random Directed Graphs with Given Degree Sequences
(University of Waterloo, 2016-08-24)A strongly connected component of a directed graph G is a maximal subgraph H of G such that for each pair of vertices u and v in H, there is a directed path from u to v and a directed path from v to u in H. A strongly ... -
On Vegh's Strongly Polynomial Algorithm for Generalized Flows
(University of Waterloo, 2014-05-22)This thesis contains an exposition of the new strongly polynomial algorithm for the generalized flow problem by Laszlo Vegh (2013). It has been a long-standing open question whether such an algorithm exists, until it was ... -
Open Shortest Path First Routing Under Random Early Detection
(Wiley, 2018-03-01)In this article, we consider a variant of Open Shortest Path First (OSPF) routing that accounts for Random Early Detection (RED), an Active Queue Management method for backbone networks. In the version of OSPF we consider ... -
Optimal Pairings on BN Curves
(University of Waterloo, 2011-08-26)Bilinear pairings are being used in ingenious ways to solve various protocol problems. Much research has been done on improving the efficiency of pairing computations. This thesis gives an introduction to the Tate pairing ... -
An Optimization Problem of Internet Routing
(University of Waterloo, 2014-09-23)As the Internet usage grows, existing network infrastructure must deal with increasing demand. One way to deal with this is to increase network capacity, and another, is to set network parameters appropriately. In this ... -
An Optimizing Pulse Sequence Compiler for NMR QIP
(University of Waterloo, 2003)Quantum information processing is a multi-disciplinary science involving physics, mathematics, computer science, and even quantum chemistry. It is centred around the idea of manipulating physical systems at the quantum ... -
Ordinary and Generalized Circulation Algebras for Regular Matroids
(University of Waterloo, 2018-09-19)Let E be a finite set, and let R(E) denote the algebra of polynomials in indeterminates (x_e)_{e in E}, modulo the squares of these indeterminates. Subalgebras of R(E) generated by homogeneous elements of degree 1 have ... -
Packing and Covering Odd (u,v)-trails in a Graph
(University of Waterloo, 2016-09-27)In this thesis, we investigate the problem of packing and covering odd $(u,v)$-trails in a graph. A $(u,v)$-trail is a $(u,v)$-walk that is allowed to have repeated vertices but no repeated edges. We call a trail \emph{odd} ...