Now showing items 211-230 of 433

    • k-Connectedness and k-Factors in the Semi-Random Graph Process 

      Koerts, Hidde (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 

      Leonardi, Christopher (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 ...
    • Key establishment --- security models, protocols and usage 

      Ustaoglu, Berkant (University of Waterloo, 2008-07-30)
      Key establishment is the process whereby two or more parties derive a shared secret, typically used for subsequent confidential communication. However, identifying the exact security requirements for key establishment ...
    • Lattice Paths 

      Ali, Irha (University of Waterloo, 2022-08-24)
      This thesis is a survey of some of the well known results in lattice path theory. Chapter 1 looks into the history of lattice paths. That is, when it began and how it was popularized. Chapter 3 focuses on general lattices ...
    • Learning Quantum States Without Entangled Measurements 

      Lowe, Angus (University of Waterloo, 2021-10-22)
      How many samples of a quantum state are required to learn a complete description of it? As we will see in this thesis, the fine-grained answer depends on the measurements available to the learner, but in general it is at ...
    • A Linear Algebraic Method on the Chromatic Symmetric Function 

      Haithcock, Evan (University of Waterloo, 2023-08-28)
      The Stanley-Stembridge conjecture is a longstanding conjecture that has evaded proof for nearly 30 years. Concerned with the e-basis expansions of the chromatic symmetric functions of unit-interval graphs, this conjecture ...
    • Linear Programming Tools and Approximation Algorithms for Combinatorial Optimization 

      Pritchard, David (University of Waterloo, 2010-01-05)
      We study techniques, approximation algorithms, structural properties and lower bounds related to applications of linear programs in combinatorial optimization. The following "Steiner tree problem" is central: given a graph ...
    • Linearly-dense classes of matroids with bounded branch-width 

      Hill, Owen (University of Waterloo, 2017-09-27)
      Let $M$ be a non-empty minor-closed class of matroids with bounded branch-width that does not contain arbitrarily large simple rank-$2$ matroids. For each non-negative integer $n$ we denote by $ex(n)$ the size of the ...
    • The Linkage Problem for Group-labelled Graphs 

      Huynh, Tony (University of Waterloo, 2009-09-24)
      This thesis aims to extend some of the results of the Graph Minors Project of Robertson and Seymour to "group-labelled graphs". Let $\Gamma$ be a group. A $\Gamma$-labelled graph is an oriented graph with its edges labelled ...
    • List 3-Coloring Graphs with No Induced P6+rP3 

      Chudnovsky, Maria; Huang, Shenwei; Spirkl, Sophie; Zhong, Mingxian (Springer Nature, 2021-01-01)
      For an integer t, we let Pt denote the t-vertex path. We write H+G for the disjoint union of two graphs H and G, and for an integer r and a graph H, we write rH for the disjoint union of r copies of H. We say that a graph ...
    • List 3-coloring Pt-free graphs with no induced 1-subdivision of K1,s 

      Chudnovsky, Maria; Spirkl, Sophie; Zhong, Mingxian (Elsevier, 2020-11)
      Let s and t be positive integers. We use Pt to denote the path with t vertices and K1,s to denote the complete bipartite graph with parts of size 1 and s respectively. The one-subdivision of K1,s is obtained by replacing ...
    • List colouring hypergraphs and extremal results for acyclic graphs 

      Pei, Martin (University of Waterloo, 2008-05-21)
      We study several extremal problems in graphs and hypergraphs. The first one is on list-colouring hypergraphs, which is a generalization of the ordinary colouring of hypergraphs. We discuss two methods for determining the ...
    • The Local Chromatic Number 

      Osang, Georg Fritz (University of Waterloo, 2014-01-23)
      A graph vertex colouring is called k-local if the number of colours used in the closed neighbourhood of each vertex is at most k. The local chromatic number of a graph is the smallest k for which the graph has a proper ...
    • Local Perspectives on Planar Colouring 

      Smith-Roberge, Evelyne (University of Waterloo, 2022-08-09)
      In 1994, Thomassen famously proved that every planar graph is 5-choosable, resolving a conjecture initially posed by Vizing and, independently, Erdos, Rubin, and Taylor in the 1970s. Later, Thomassen proved that every ...
    • Local properties of graphs with large chromatic number 

      Davies, James (University of Waterloo, 2022-08-31)
      This thesis deals with problems concerning the local properties of graphs with large chromatic number in hereditary classes of graphs. We construct intersection graphs of axis-aligned boxes and of lines in $\mathbb{R}^3$ ...
    • Local Structure for Vertex-Minors 

      McCarty, Rose (University of Waterloo, 2021-10-12)
      This thesis is about a conjecture of Geelen on the structure of graphs with a forbidden vertex-minor; the conjecture is like the Graph Minors Structure Theorem of Robertson and Seymour but for vertex-minors instead of ...
    • Low-Rank Plus Sparse Decompositions of Large-Scale Matrices via Semidefinite Optimization 

      Gong, Rui (University of Waterloo, 2023-05-19)
      We study the problem of decomposing a symmetric matrix into the sum of a low-rank symmetric positive semidefinite matrix and a tridiagonal matrix, and a relaxation which looks for symmetric positive semidefinite matrices ...
    • LP-based Approximation Algorithms for the Capacitated Facility Location Problem 

      Blanco Sandoval, Marco David (University of Waterloo, 2012-05-18)
      The capacitated facility location problem is a well known problem in combinatorial optimization and operations research. In it, we are given a set of clients and a set of possible facility locations. Each client has a ...
    • MAC Constructions: Security Bounds and Distinguishing Attacks 

      Mandal, Avradip (University of Waterloo, 2007-05-18)
      We provide a simple and improved security analysis of PMAC, a Parallelizable MAC (Message Authentication Code) defined over arbitrary messages. A similar kind of result was shown by Bellare, Pietrzak and Rogaway at ...
    • Machine-Level Software Optimization of Cryptographic Protocols 

      Fishbein, Dieter (University of Waterloo, 2014-04-30)
      This work explores two methods for practical cryptography on mobile devices. The first method is a quantum-resistant key-exchange protocol proposed by Jao et al.. As the use of mobile devices increases, the deployment of ...

      UWSpace

      University of Waterloo Library
      200 University Avenue West
      Waterloo, Ontario, Canada N2L 3G1
      519 888 4883

      All items in UWSpace are protected by copyright, with all rights reserved.

      DSpace software

      Service outages