Browsing Combinatorics and Optimization by Title
Now showing items 332-351 of 435
-
Properties of Stable Matchings
(University of Waterloo, 2010-12-17)Stable matchings were introduced in 1962 by David Gale and Lloyd Shapley to study the college admissions problem. The seminal work of Gale and Shapley has motivated hundreds of research papers and found applications in ... -
Pure Pairs VI. Excluding an Ordered Tree.
(Society for Industrial and Applied Mathematics Journal on Discrete Mathematics, 2022-01)A pure pair in a graph G is a pair (Z1,Z2) of disjoint sets of vertices such that either every vertex in Z1 is adjacent to every vertex in Z2, or there are no edges between Z1 and Z2. With Maria Chudnovsky, we recently ... -
Pure pairs. I. Trees and linear anticomplete pairs
(Elsevier, 2020-12-02)The Erdős-Hajnal conjecture asserts that for every graph H there is a constant c > 0 such that every graph G that does not contain H as an induced subgraph has a clique or stable set of cardinality at least |G|c. In this ... -
Pure pairs. II. Excluding all subdivisions of a graph
(Springer Nature, 2021-06-01)We prove for every graph H there exists ɛ > 0 such that, for every graph G with |G|≥2, if no induced subgraph of G is a subdivision of H, then either some vertex of G has at least ɛ|G| neighbours, or there are two disjoint ... -
Pure pairs. III. Sparse graphs with no polynomial-sized anticomplete pairs
(Wiley, 2020-11)A graph is H-free if it has no induced subgraph isomorphic to H, and |G| denotes the number of vertices of G. A conjecture of Conlon, Sudakov and the second author asserts that: - For every graph H, there exists ∈ > 0 ... -
A Puzzle-Based Synthesis Algorithm For a Triple Intersection of Schubert Varieties
(University of Waterloo, 2010-01-29)This thesis develops an algorithm for the Schubert calculus of the Grassmanian. Specifically, we state a puzzle-based, synthesis algorithm for a triple intersection of Schubert varieties. Our algorithm is a reformulation ... -
A quadratic programming approach to find faces in robust nonnegative matrix factorization
(University of Waterloo, 2017-08-29)Nonnegative matrix factorization (NMF) is a popular dimensionality reduction technique because it is easily interpretable and can discern useful features. For a given matrix M (dimension n x m) whose entries are nonnegative ... -
Quadratically Dense Matroids
(University of Waterloo, 2020-07-08)This thesis is concerned with finding the maximum density of rank-$n$ matroids in a minor-closed class. The extremal function of a non-empty minor-closed class $\mathcal M$ of matroids which excludes a rank-2 uniform ... -
Quantum algorithms for searching, resampling, and hidden shift problems
(University of Waterloo, 2012-09-21)This thesis is on quantum algorithms. It has three main themes: (1) quantum walk based search algorithms, (2) quantum rejection sampling, and (3) the Boolean function hidden shift problem. The first two parts deal with ... -
Quantum Compression and Quantum Learning via Information Theory
(University of Waterloo, 2020-12-21)This thesis consists of two parts: quantum compression and quantum learning theory. A common theme between these problems is that we study them through the lens of information theory. We first study the task of visible ... -
Quantum Cost Models for Cryptanalysis of Isogenies
(University of Waterloo, 2019-05-01)Isogeny-based cryptography uses keys large enough to resist a far-future attack from Tani’s algorithm, a quantum random walk on Johnson graphs. The key size is based on an analysis in the query model. Queries do not ... -
Quantum independence and chromatic numbers
(University of Waterloo, 2019-08-28)In this thesis we are studying the cases when quantum independence and quantum chromatic numbers coincide with or differ from their classical counterparts. Knowing about the relation of chromatic numbers separation to the ... -
Quantum Information Processing with Adversarial Devices
(University of Waterloo, 2010-06-09)We consider several applications in black-box quantum computation in which untrusted physical quantum devices are connected together to produce an experiment. By examining the outcome statistics of such an experiment, and ... -
Quantum Random Access Codes with Shared Randomness
(University of Waterloo, 2009-05-22)We consider a communication method, where the sender encodes n classical bits into 1 qubit and sends it to the receiver who performs a certain measurement depending on which of the initial bits must be recovered. This ... -
Quantum Rejection Sampling
(University of Waterloo, 2015-01-21)Let H be a finite dimensional Hilbert space and ρ, σ ∈ D(H) be quantum states in H such that S(ρ||σ) is finite. In this thesis, we consider the following communication task involving two parties Alice and Bob. Suppose ... -
Quantum Speed-ups for Boolean Satisfiability and Derivative-Free Optimization
(University of Waterloo, 2014-04-21)In this thesis, we have considered two important problems, Boolean satisfiability (SAT) and derivative free optimization in the context of large scale quantum computers. In the first part, we survey well known classical ... -
Quantum State Transfer in Graphs
(University of Waterloo, 2014-08-13)Let X be a graph, A its adjacency matrix, and t a non-negative real number. The matrix exp(i t A) determines the evolution in time of a certain quantum system defined on the graph. It represents a continuous-time quantum ... -
Quantum Walks and Pretty Good State transfer on Paths
(University of Waterloo, 2019-08-23)Quantum computing is believed to provide many advantages over traditional computing, particularly considering the speed at which computations can be performed. One of the challenges that needs to be resolved in order to ... -
Quantum Walks on Oriented Graphs
(University of Waterloo, 2019-01-11)This thesis extends results about periodicity and perfect state transfer to oriented graphs. We prove that if a vertex a is periodic, then elements of the eigenvalue support lie in Z √∆ for some squarefree negative ... -
Quantum Walks on Strongly Regular Graphs
(University of Waterloo, 2010-08-30)This thesis studies the transition matrix of a quantum walk on strongly regular graphs. It is proposed by Emms, Hancock, Severini and Wilson in 2006, that the spectrum of a matrix based on the amplitudes of walks in the ...