Browsing Combinatorics and Optimization by Title
Now showing items 372-391 of 435
-
Security in Key Agreement: Two-Party Certificateless Schemes
(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
(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
(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
(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
(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
(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
(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
(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
(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
(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
(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
(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
(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
(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 ... -
Single Commodity Flow Algorithms for Lifts of Graphic and Cographic Matroids
(University of Waterloo, 2013-01-23)Consider a binary matroid M given by its matrix representation. We show that if M is a lift of a graphic or a cographic matroid, then in polynomial time we can either solve the single commodity flow problem for M or find ... -
Smoothening Functions and the Homomorphism Learning Problem
(University of Waterloo, 2020-09-02)This thesis is an exploration of certain algebraic and geometrical aspects of the Learning With Errors (LWE) problem introduced in Reg05. On the algebraic front, we view it as a Learning Homomorphisms with Noise problem, ... -
Solving Saddle Point Formulations of Linear Programs with Frank-Wolfe
(University of Waterloo, 2023-08-24)The problem of solving a linear program (LP) is ubiquitous in industry, yet in recent years the size of linear programming problems has grown and continues to do so. State-of-the-art LP solvers make use of the Simplex ... -
Some Upper and Lower Bounds regarding Query Complexity
(University of Waterloo, 2017-08-29)Query complexity is one of the several notions of complexity de ned to measure the cost of algorithms. It plays an important role in demonstrating the quantum advantage, that quantum computing is faster than classical ... -
Sparsity in Critical Graphs with Small Clique Number
(University of Waterloo, 2020-08-27)In 1998, Reed conjectured that for every graph $G$, $\chi(G) \leq \lceil \frac{1}{2}(\Delta(G)+1+\omega(G)) \rceil$, and proved that there exists $\varepsilon > 0$ such that $\chi(G) \leq \lceil (1 - \varepsilon)(\Delta(G)+1) ... -
Spectral Aspects of Cocliques in Graphs
(University of Waterloo, 2014-05-01)This thesis considers spectral approaches to finding maximum cocliques in graphs. We focus on the relation between the eigenspaces of a graph and the size and location of its maximum cocliques. Our main result concerns ...