Browsing Combinatorics and Optimization by Title
Now showing items 36-55 of 434
-
Batch Verification of Elliptic Curve Digital Signatures
(University of Waterloo, 2015-04-20)This thesis investigates the efficiency of batching the verification of elliptic curve signatures. The first signature scheme considered is a modification of ECDSA proposed by Antipa et al.\ along with a batch verification ... -
Bi-objective short-term scheduling in a rolling horizon framework: a priori approaches with alternative operational objectives
(Elsevier, 2019-11)This study addresses short-term scheduling problems with throughput and make-span as conflicting objectives, focusing on a priori multi-objective methods. Two contributions are presented. The first contribution is to propose ... -
Binary Adder Circuits of Asymptotically Minimum Depth, Linear Size, and Fan-Out Two
(Association for Computing Machinery, 2018-01)We consider the problem of constructing fast and small binary adder circuits. Among widely used adders, the Kogge-Stone adder is often considered the fastest, because it computes the carry bits for two n-bit numbers (where ... -
Bipartite Distance-Regular Graphs of Diameter Four
(University of Waterloo, 2014-08-11)Using a method by Godsil and Roy, bipartite distance-regular graphs of diameter four can be used to construct $\{0,\alpha\}$-sets, a generalization of the widely applied equiangular sets and mutually unbiased bases. In ... -
Bipartite Quantum Walks and the Hamiltonian
(University of Waterloo, 2023-09-26)We study a discrete quantum walk model called bipartite walks via a spectral approach. A bipartite walk is determined by a unitary matrix U, i.e., the transition matrix of the walk. For every transition matrix U, there is ... -
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 ...