Browsing Combinatorics and Optimization by Title
Now showing items 41-60 of 435
-
A Blueprint for Semidefinite Relaxations of Binary-Constrained Quadratic Programs Computing tight bounds on NP-hard problems using ADMM
(University of Waterloo, 2020-12-18)This thesis looks at the solution techniques of two NP-hard, large scale problems, the quadratic assignment problem, QAP, and the side chain positioning, SCP, problem. We summarize existing approaches from and look at the ... -
Boneh-Boyen Signatures and the Strong Diffie-Hellman Problem
(University of Waterloo, 2009-01-22)The Boneh-Boyen signature scheme is a short signature scheme which is provably secure in the standard model under the q-Strong Diffie-Hellman (SDH) assumption. The primary objective of this thesis is to examine the ... -
Brick Generation and Conformal Subgraphs
(University of Waterloo, 2016-04-15)A nontrivial connected graph is matching covered if each of its edges lies in a perfect matching. Two types of decompositions of matching covered graphs, namely ear decompositions and tight cut decompositions, have played ... -
Building Networks in the Face of Uncertainty
(University of Waterloo, 2011-08-26)The subject of this thesis is to study approximation algorithms for some network design problems in face of uncertainty. We consider two widely studied models of handling uncertainties - Robust Optimization and Stochastic ... -
The Capacitated Matroid Median Problem
(University of Waterloo, 2018-05-18)In this thesis, we study the capacitated generalization of the Matroid Median Problem which is a generalization of the classical clustering problem called the k-Median problem. In the capacitated matroid median problem, ... -
Capacitated Network Design on Outerplanar Graphs
(University of Waterloo, 2020-09-03)Network design problems model the efficient allocation of resources like routers, optical fibres, roads, canals etc. to effectively construct and operate critical infrastructures. In this thesis, we consider the capacitated ... -
Caterpillars in Erdős–Hajnal
(Elsevier, 2019-05)Let T be a tree such that all its vertices of degree more than two lie on one path; that is, T is a caterpillar subdivision. We prove that there exists ε > 0 such that for every graph G with |V(G)| ≥ 2 not containing T as ... -
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 ... -
A Characterization of LYM and Rank Logarithmically Concave Partially Ordered Sets and Its Applications
(University of Waterloo, 2010-01-21)The LYM property of a finite standard graded poset is one of the central notions in Sperner theory. It is known that the product of two finite standard graded posets satisfying the LYM properties may not have the LYM ... -
Characterization of non-universal two-qubit Hamiltonians
(University of Waterloo, 2009-12-16)It is known that almost all 2-qubit gates are universal for quantum computing (Lloyd 1995; Deutsch, Barenco, Eckert 1995). However, an explicit characterization of non-universal 2-qubit gates is not known. We consider a ... -
Chosen Ciphertext Security from Zero Knowledge Proofs
(University of Waterloo, 2023-08-24)When designing encryption schemes, there are different levels of security that one can achieve. Of the two main security levels, cryptographers generally strive for the stronger notion of chosen ciphertext attack (CCA) ... -
Circle Graph Obstructions
(University of Waterloo, 2017-08-31)In this thesis we present a self-contained proof of Bouchet’s characterization of the class of circle graphs. The proof uses signed graphs and is analogous to Gerards’ graphic proof of Tutte’s excluded-minor characterization ... -
Classical and Quantum Algorithms for Isogeny-based Cryptography
(University of Waterloo, 2015-09-30)Isogeny-based cryptography using supersingular elliptic curves --- most prominently, the constructions of De Feo-Jao-Plut --- is one of the few practical candidates for post-quantum public key cryptography. Its formidable ... -
Classical Authenticated Key Exchange and Quantum Cryptography
(University of Waterloo, 2009-03-16)Cryptography plays an integral role in secure communication and is usually the strongest link in the chain of security. Yet security problems abound in electronic communication: spyware, phishing, denial of service, and ... -
Clifford Simulation: Techniques and Applications
(University of Waterloo, 2021-05-28)Despite the widespread belief that quantum computers cannot be efficiently simulated classically, efficient simulation is known to be possible in certain restricted regimes. In particular, the Gottesman-Knill theorem states ... -
Clique minors in dense matroids
(University of Waterloo, 2022-09-23)The objective of this thesis is to bound the number of points a $U_{2,\ell+2}$- and $M(K_{k+1})$-minor-free matroid has. We first prove that a sufficiently large matroid will contain a structure called a tower. We then use ... -
Cliques, Degrees, and Coloring: Expanding the ω, Δ, χ paradigm
(University of Waterloo, 2019-08-09)Many of the most celebrated and influential results in graph coloring, such as Brooks' Theorem and Vizing's Theorem, relate a graph's chromatic number to its clique number or maximum degree. Currently, several of the most ... -
Collision Finding with Many Classical or Quantum Processors
(University of Waterloo, 2011-08-31)In this thesis, we investigate the cost of finding collisions in a black-box function, a problem that is of fundamental importance in cryptanalysis. Inspired by the excellent performance of the heuristic rho method of ... -
Coloring Algorithms for Graphs and Hypergraphs with Forbidden Substructures
(University of Waterloo, 2022-04-18)This thesis mainly focus on complexity results of the generalized version of the $r$-Coloring Problem, the $r$-Pre-Coloring Extension Problem and the List $r$-Coloring Problem restricted to hypergraphs and ordered graphs ... -
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 ...