Now showing items 352-371 of 433

    • Ramsey-nice families of graphs 

      Aharoni, Ron; Alon, Noga; Amir, Michal; Haxell, Penny; Hefetz, Dan; Jiang, Zilin; Kronenberg, Gal; Naor, Alon (Elsevier, 2018-08)
      For a finite family $\cF$ of fixed graphs let $R_k(\cF)$ be the smallest integer $n$ for which every $k$-coloring of the edges of the complete graph $K_n$ yields a monochromatic copy of some $F\in\cF$. We say that $\cF$ ...
    • Rayleigh Property of Lattice Path Matroids 

      Xu, Yan (University of Waterloo, 2015-09-22)
      In this work, we studied the class of lattice path matroids $\mathcal{L}$, which was first introduced by J.E. Bonin. A.D. Mier, and M. Noy in [\ref{Bonin 2002}]. Lattice path matroids are transversal, and $\mathcal{L}$ is ...
    • Real equiangular lines and related codes 

      Winnick, Samuel (University of Waterloo, 2020-01-24)
      We consider real equiangular lines and related codes. The driving question is to find the maximum number of equiangular lines in a given dimension. In the real case, this is controlled by combinatorial phenomena, and until ...
    • Recognizing Even-Cycle and Even-Cut Matroids 

      Heo, Cheolwon (University of Waterloo, 2016-04-27)
      Even-cycle and even-cut matroids are classes of binary matroids that generalize respectively graphic and cographic matroids. We give algorithms to check membership for these classes of matroids. We assume that the matroids ...
    • Recovery Guarantees for Graph Clustering Problems 

      Majmudar, Jimit (University of Waterloo, 2021-12-06)
      Graph clustering is widely-studied unsupervised learning problem in which the task is to group similar entities together based on observed pairwise entity interactions. This problem has applications in diverse domains such ...
    • Regularization Using a Parameterized Trust Region Subproblem 

      Grodzevich, Oleg (University of Waterloo, 2004)
      We present a new method for regularization of ill-conditioned problems that extends the traditional trust-region approach. Ill-conditioned problems arise, for example, in image restoration or mathematical processing of ...
    • Relaxations of the Maximum Flow Minimum Cut Property for Ideal Clutters 

      Ferchiou, Zouhaier (University of Waterloo, 2021-01-29)
      Given a family of sets, a covering problem consists of finding a minimum cost collection of elements that hits every set. This objective can always be bound by the maximum number of disjoint sets in the family, we refer ...
    • Representations of even-cycle and even-cut matroids 

      Heo, Cheolwon (University of Waterloo, 2021-08-27)
      In this thesis, two classes of binary matroids will be discussed: even-cycle and even-cut matroids, together with problems which are related to their graphical representations. Even-cycle and even-cut matroids can be ...
    • Resolution of Ties in Parametric Quadratic Programming 

      Wang, Xianzhi (University of Waterloo, 2004)
      We consider the convex parametric quadratic programming problem when the end of the parametric interval is caused by a multiplicity of possibilities ("ties"). In such cases, there is no clear way for the proper active ...
    • Results on Chromatic Polynomials Inspired by a Correlation Inequality of G.E. Farr 

      McKay, Ghislain (University of Waterloo, 2018-09-25)
      In1993 Graham Farr gave a proof of a correlation inequality involving colourings of graphs. His work eventually led to a conjecture that number of colourings of a graph with certain properties gave a log-concave sequence. ...
    • Revisiting the security model for aggregate signature schemes 

      Lacharité, Marie-Sarah (University of Waterloo, 2014-05-26)
      Aggregate signature schemes combine the digital signatures of multiple users on different messages into one single signature. The Boneh-Gentry-Lynn-Shacham (BGLS) aggregate signature scheme is one such scheme, based on ...
    • Rigidity of near-optimal superdense coding protocols 

      Zhou, Xingyu (University of Waterloo, 2023-09-19)
      Rigidity in quantum information theory refers to the stringent constraints underlying optimal or near-optimal performance in certain quantum tasks. This property plays a crucial role in verifying untrusted quantum devices ...
    • 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 ...

      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