Browsing Combinatorics and Optimization by Title
Now showing items 312-331 of 436
-
Perfect Hash Families: Constructions and Applications
(University of Waterloo, 2003)Let <b>A</b> and <b>B</b> be finite sets with |<b>A</b>|=<i>n</i> and |<b>B</b>|=<i>m</i>. An (<i>n</i>,<i>m</i>,<i>w</i>)-<i>perfect hash</i> family</i> is a collection <i>F</i> of functions from <b>A</b> to <b>B</b> ... -
Piercing axis-parallel boxes
(The Electronic Journal of Combinatorics, 2018)Let F be a finite family of axis-parallel boxes in Rd such that F contains no k + 1 pairwise disjoint boxes. We prove that if F contains a subfamily M of k pairwise disjoint boxes with the property that for every F E F ... -
Planar graphs without 3-cycles and with 4-cycles far apart are 3-choosable
(University of Waterloo, 2016-09-16)A graph G is said to be L-colourable if for a given list assignment L = {L(v)|v ∈ V (G)} there is a proper colouring c of G such that c(v) ∈ L(v) for all v in V (G). If G is L-colourable for all L with |L(v)| ≥ k for all ... -
Plethysms of Chromatic and Tutte Symmetric Functions
(The Electronic Journal of Combinatorics, 2022)Plethysm is a fundamental operation in symmetric function theory, derived directly from its connection with representation theory. However, it does not admit a simple combinatorial interpretation, and finding coefficients ... -
Polyhedral Diameters and Applications to Optimization
(University of Waterloo, 2022-09-01)The Simplex method is the most popular algorithm for solving linear programs (LPs). Geometrically, it moves from an initial vertex solution to an improving neighboring one, selected according to a pivot rule. Despite decades ... -
Polynomial bounds for chromatic number II: Excluding a star-forest
(Wiley, 2022-10)The Gyárfás–Sumner conjecture says that for every forest H, there is a function fH such that if G is H-free then x(G) ≤ fH(w(G)) (where x,w are the chromatic number and the clique number of G). Louis Esperet conjectured ... -
Polynomial bounds for chromatic number. III. Excluding a double star
(Wiley, 2022-10)A “double star” is a tree with two internal vertices. It is known that the Gyárfás-Sumner conjecture holds for double stars, that is, for every double star H, there is a function fH such that if G does not contain H as ... -
Portfolio Selection Under Nonsmooth Convex Transaction Costs
(University of Waterloo, 2006)We consider a portfolio selection problem in the presence of transaction costs. Transaction costs on each asset are assumed to be a convex function of the amount sold or bought. This function can be nondifferentiable ... -
Post-Quantum Account Recovery for Passwordless Authentication
(University of Waterloo, 2023-04-24)WebAuthn is a passwordless authentication protocol which allows users to authenticate to online services using public-key cryptography. Users prove their identity based on possession of a private key, which is stored on a ... -
A post-quantum digital signature scheme based on supersingular isogenies
(University of Waterloo, 2017-09-20)We present the first general-purpose digital signature scheme based on supersingular elliptic curve isogenies secure against quantum adversaries in the quantum random oracle model with small key sizes. This scheme is ... -
Post-Quantum Security of Authenticated Key Establishment Protocols
(University of Waterloo, 2016-04-20)We present a security model for authenticated key establishment that allows for quantum interactions between the adversary and quantum oracles that emulate classical parties, resulting in a truly post-quantum security ... -
Postman Problems on Mixed Graphs
(University of Waterloo, 2003)The <i>mixed postman problem</i> consists of finding a minimum cost tour of a mixed graph <i>M</i> = (<i>V</i>,<i>E</i>,<i>A</i>) traversing all its edges and arcs at least once. We prove that two well-known linear ... -
Practical Lattice Cryptosystems: NTRUEncrypt and NTRUMLS
(University of Waterloo, 2015-12-22)Public key cryptography, as deployed on the internet today, stands on shaky ground. For over twenty years now it has been known that the systems in widespread use are insecure against adversaries equipped with quantum ... -
Preprocessing and Reduction for Semidefinite Programming via Facial Reduction: Theory and Practice
(University of Waterloo, 2013-11-26)Semidefinite programming is a powerful modeling tool for a wide range of optimization and feasibility problems. Its prevalent use in practice relies on the fact that a (nearly) optimal solution of a semidefinite program ... -
Primal Cutting Plane Methods for the Traveling Salesman Problem
(University of Waterloo, 2017-04-26)Most serious attempts at solving the traveling salesman problem (TSP) are based on the dual fractional cutting plane approach, which moves from one lower bound to the next. This thesis describes methods for implementing ... -
A Primal Dual Algorithm On 2-Steiner Graphs
(University of Waterloo, 2018-01-23)The Steiner Tree Problem is a fundamental network design problem, where the goal is to connect a subset of terminals of a given network at minimum cost. A major open question regarding this problem, is proving that the ... -
A Primer on Cryptographic Multilinear Maps and Code Obfuscation
(University of Waterloo, 2015-09-23)The construction of cryptographic multilinear maps and a general-purpose code obfuscator were two long-standing open problems in cryptography. It has been clear for a number of years that constructions of these two ... -
Probabilistic Choice Models for Product Pricing Using Reservation Prices
(University of Waterloo, 2007-01-22)The problem of pricing a product line to maximize profits is an important challenge faced by many companies. To address this problem, we discuss four different probabilistic choice models that are based on reservation ... -
Proof of the Kalai-Meshulam conjecture
(Springer Nature, 2020-07-01)Let G be a graph, and let fG be the sum of (−1)∣A∣, over all stable sets A. If G is a cycle with length divisible by three, then fG = ±2. Motivated by topological considerations, G. Kalai and R. Meshulam [8] made the ... -
Properties of graphs with large girth
(University of Waterloo, 2008-01-24)This thesis is devoted to the analysis of a class of iterative probabilistic algorithms in regular graphs, called locally greedy algorithms, which will provide bounds for graph functions in regular graphs with ...