Now showing items 364-383 of 433

    • Sandwich and probe problems for excluding paths 

      Figueiredo, Celina Miraglia Herrera de; Spirkl, Sophie (Elsevier, 2018-12-31)
      Let Pk denote an induced path on k vertices. For k ≥ 5, we show that the Pk-free sandwich problem, partitioned probe problem, and unpartitioned probe problem are NP-complete. For k ≤ 4, it is known that the Pk-free sandwich ...
    • The Sandwich Problem for Decompositions and Almost Monotone Properties 

      Chudnovsky, Maria; Figueiredo, Celina Miraglia Herrera de; Spirkl, Sophie (Springer Nature, 2018)
      We consider the graph sandwich problem and introduce almost monotone properties, for which the sandwich problem can be reduced to the recognition problem. We show that the property of containing a graph in C as an induced ...
    • Santa Claus, Machine Scheduling and Bipartite Hypergraphs 

      Jay, Andrew (University of Waterloo, 2020-01-10)
      Here we discuss two related discrete optimization problems, a prominent problem in scheduling theory, makespan minimization on unrelated parallel machines, and the other a fair allocation problem, the Santa Claus problem. ...
    • Scarf's Theorem and Applications in Combinatorics 

      Rioux, Caroline (University of Waterloo, 2006-12-19)
      A theorem due to Scarf in 1967 is examined in detail. Several versions of this theorem exist, some which appear at first unrelated. Two versions can be shown to be equivalent to a result due to Sperner in 1928: for a ...
    • The search for an excluded minor characterization of ternary Rayleigh matroids 

      Phillips, Stephanie (University of Waterloo, 2008-01-24)
      Rayleigh matroids are a class of matroids with sets of bases that satisfy a strong negative correlation property. Interesting characteristics include the existence of an efficient algorithm for sampling the bases of a ...
    • Security Analysis of Isogeny-Based Cryptosystems 

      Leonardi, Christopher (University of Waterloo, 2020-08-20)
      Let $E$ be a supersingular elliptic curve over a finite field. In this document we study public-key encryption schemes which use non-constant rational maps from $E$. The purpose of this study is to determine if such ...
    • Security in Key Agreement: Two-Party Certificateless Schemes 

      Swanson, Colleen Marie (University of Waterloo, 2008-12-22)
      The main goal of cryptography is to enable secure communication over a public channel; often a secret shared among the communicating parties is used to achieve this. The process by which these parties agree on such a shared ...
    • Security Models and Proofs for Key Establishment Protocols 

      Ng, Eddie M. (University of Waterloo, 2005)
      In this thesis we study the problem of secure key establishment, motivated by the construction of secure channels protocols to protect information transmitted over an open network. In the past, the purported security of ...
    • Self-Complementary Arc-Transitive Graphs and Their Imposters 

      Mullin, Natalie Ellen (University of Waterloo, 2009-01-28)
      This thesis explores two infinite families of self-complementary arc-transitive graphs: the familiar Paley graphs and the newly discovered Peisert graphs. After studying both families, we examine a result of Peisert which ...
    • Self-Dual Graphs 

      Hill, Alan (University of Waterloo, 2002)
      The study of self-duality has attracted some attention over the past decade. A good deal of research in that time has been done on constructing and classifying all self-dual graphs and in particular polyhedra. We ...
    • Semidefinite Facial Reduction for Low-Rank Euclidean Distance Matrix Completion 

      Krislock, Nathan (University of Waterloo, 2010-04-27)
      The main result of this thesis is the development of a theory of semidefinite facial reduction for the Euclidean distance matrix completion problem. Our key result shows a close connection between cliques in the graph of ...
    • Semidefinite Programming Relaxations of the Simplified Wasserstein Barycenter Problem: An ADMM Approach 

      Cheng, Jiahui (University of Waterloo, 2023-05-04)
      The Simplified Wasserstein Barycenter problem, the problem of picking k points each chosen from a distinct set of n points as to minimize the sum of distances to their barycenter, finds applications in various areas of ...
    • Sensitivity Analysis and Robust Optimization: A Geometric Approach for the Special Case of Linear Optimization 

      Im, Jiyoung (University of Waterloo, 2018-12-21)
      In this thesis, we study the special case of linear optimization to show what may affect the sensitivity of the optimal value function under data uncertainty. In this special case, we show that the robust optimization ...
    • Separable State Discrimination Using Local Quantum Operations and Classical Communication 

      Mancinska, Laura (University of Waterloo, 2013-08-30)
      In this thesis we study the subset of quantum operations that can be implemented using only local quantum operations and classical communication (LOCC). This restricted paradigm serves as a tool to study not only quantum ...
    • Sequences of Trees and Higher-Order Renormalization Group Equations 

      Dugan, William (University of Waterloo, 2019-08-27)
      In 1998, Connes and Kreimer introduced a combinatorial Hopf algebra HCK on the vector space of forests of rooted trees that precisely explains the phenomenon of renormalization in quantum field theory. This Hopf algebra ...
    • Short Directed Cycles in Bipartite Digraphs 

      Seymour, Paul; Spirkl, Sophie (Springer Nature, 2020-08-01)
      The Caccetta-Häggkvist conjecture implies that for every integer k ≥ 1, if G is a bipartite digraph, with n vertices in each part, and every vertex has out-degree more than n/(k+1), then G has a directed cycle of length ...
    • Signature Schemes in the Quantum Random-Oracle Model 

      Eaton, Edward (University of Waterloo, 2017-04-25)
      A signature scheme is a fundamental component in modern digital communication. It allows for authenticated messages, without which it would be nearly impossible to ensure security when using most modern technologies. ...
    • Signing with Codes 

      Masárová, Zuzana (University of Waterloo, 2014-01-22)
      Code-based cryptography is an area of classical cryptography in which cryptographic primitives rely on hard problems and trapdoor functions related to linear error-correcting codes. Since its inception in 1978, the area ...
    • Simple Drawings of Kn from Rotation Systems 

      Sullivan, Matthew A. (University of Waterloo, 2021-10-06)
      A complete rotation system on n vertices is a collection of n cyclic permutations of the elements [n]\{i}, for i∈[n]. If D is a drawing of a labelled graph, then a rotation at vertex v is the cyclic ordering of the edges ...
    • Simple Termination Criteria for Stochastic Gradient Descent Algorithm 

      Baghal, Sina (University of Waterloo, 2021-04-09)
      Stochastic gradient descent (SGD) algorithm is widely used in modern mathematical optimization. Because of its scalability and ease of implementation, SGD is usually preferred to other methods including the gradient descent ...

      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