Browsing Combinatorics and Optimization by Title
Now showing items 194-213 of 434
-
Ideal Clutters
(University of Waterloo, 2018-04-24)Let E be a finite set of elements, and let C be a family of subsets of E called members. We say that C is a clutter over ground set E if no member is contained in another. The clutter C is ideal if every extreme point of ... -
Implementing the Castryck-Decru attack on SIDH with general primes
(University of Waterloo, 2024-01-09)With the rapid progress of quantum computers in recent years, efforts have been made to standardize new public-key cryptographic protocols which would be secure against them. One of the schemes in contention was Supersingular ... -
Implementing the Schoof-Elkies-Atkin Algorithm with NTL
(University of Waterloo, 2013-04-30)In elliptic curve cryptography, cryptosystems are based on an additive subgroup of an elliptic curve defined over a finite field, and the hardness of the Elliptic Curve Discrete Logarithm Problem is dependent on the order ... -
Implicit Loss of Surjectivity and Facial Reduction: Theory and Applications
(University of Waterloo, 2023-03-09)Facial reduction, pioneered by Borwein and Wolkowicz, is a preprocessing method that is commonly used to obtain strict feasibility in the reformulated, reduced constraint system. The importance of strict feasibility is ... -
Improved approximation guarantees for lower-bounded facility location problem
(University of Waterloo, 2010-09-28)We consider the lower-bounded facility location (LBFL) problem (, also known as load-balanced facility location), which is a generalization of uncapacitated facility location (UFL) problem where each open facility is ... -
Improving post-quantum cryptography through cryptanalysis
(University of Waterloo, 2020-07-15)Large quantum computers pose a threat to our public-key cryptographic infrastructure. The possible responses are: Do nothing; accept the fact that quantum computers might be used to break widely deployed protocols. Mitigate ... -
Independent Sets and Eigenspaces
(University of Waterloo, 2004)The problems we study in this thesis arise in computer science, extremal set theory and quantum computing. The first common feature of these problems is that each can be reduced to characterizing the independent sets ... -
Induced Binary Submatroids
(University of Waterloo, 2021-07-21)The notion of induced subgraphs is extensively studied in graph theory. An example is the famous Gy\'{a}rf\'{a}s-Sumner conjecture, which asserts that given a tree $T$ and a clique $K$, there exists a constant $c$ such ... -
Induced Subgraphs and Tree Decompositions III. Three-Path-Configurations and Logarithmic Treewidth.
(Advances in Combinatorics, 2022-09-09)A theta is a graph consisting of two non-adjacent vertices and three internally disjoint paths between them, each of length at least two. For a family H of graphs, we say a graph G is H-free if no induced subgraph of G is ... -
Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes
(Elsevier, 2020-01)We prove a conjecture of András Gyárfás, that for all k, l, every graph with clique number at most κ and sufficiently large chromatic number has an odd hole of length at least ℓ. -
Induction Relations in the Symmetric Groups and Jucys-Murphy Elements
(University of Waterloo, 2018-08-16)Transitive factorizations faithfully encode many interesting objects. The well-known ones include ramified coverings of the sphere and hypermaps. Enumeration of specific classes of such objects have been known for quite ... -
Infinite graphs, graph-like spaces and B-matroids
(University of Waterloo, 2011-01-19)The central theme of this thesis is to prove results about infinite mathematical objects by studying the behaviour of their finite substructures. In particular, we study B-matroids, which are an infinite generalization ... -
Inner approximation of convex cones via primal-dual ellipsoidal norms
(University of Waterloo, 2016-05-13)We study ellipsoids from the point of view of approximating convex sets. Our focus is on finding largest volume ellipsoids with specified centers which are contained in certain convex cones. After reviewing the related ... -
An integrated personnel allocation and machine scheduling problem for industrial size multipurpose plants
(Elsevier, 2018-01-01)This paper describes the development and implementation of an optimization model to solve the integrated problem of personnel allocation and machine scheduling for industrial size multipurpose plants. Although each of these ... -
Interior-Point Algorithms Based on Primal-Dual Entropy
(University of Waterloo, 2006)We propose a family of search directions based on primal-dual entropy in the context of interior point methods for linear programming. This new family contains previously proposed search directions in the context of ... -
An Isogeny-Based Adaptor Signature Using SQISign
(University of Waterloo, 2022-04-19)Transactions on blockchains can prove very costly, so as a solution to avoid these large costs, schemes involving payment channel networks have been developed. One approach to implementing these off-chain forms of payment ... -
Iterative Rounding Approximation Algorithms in Network Design
(University of Waterloo, 2010-05-21)Iterative rounding has been an increasingly popular approach to solving network design optimization problems ever since Jain introduced the concept in his revolutionary 2-approximation for the Survivable Network Design ... -
Jaeger’s Strong 3-Flow Conjecture for Graphs in Low Genus Surfaces
(University of Waterloo, 2020-05-05)In 1972, Tutte posed the 3-Flow Conjecture: that all 4-edge-connected graphs have a nowhere zero 3-flow. This was extended by Jaeger et al. (1992) to allow vertices to have a prescribed, possibly non-zero difference (modulo ... -
k-Connectedness and k-Factors in the Semi-Random Graph Process
(University of Waterloo, 2022-12-20)The semi-random graph process is a single-player graph game where the player is initially presented an edgeless graph with n vertices. In each round, the player is offered a vertex u uniformly at random and subsequently ... -
Key Compression for Isogeny-Based Cryptosystems
(University of Waterloo, 2016-04-21)We present a method for key compression in quantum-resistant isogeny-based cryptosystems, which reduces storage and transmission costs of per-party public information by a factor of two, with no effect on the security level ...