Title: Additive Complexity of Infinite Words
Abstract: An openproblem in combinatorics on words is whether there exists an infinite word on a finite integer alphabet avoiding additive squares, i.e., a word such that any two adjacent factors of the same length must have different sums. Motivated by this problem, Ardal, Brown, Jungi\\'{c}, and Sahasrabudhe studied infinite words where the number of distinct sums exhibited by factors of the same length is bounded by a constant that depends only on the word. Such words are said to have bounded additive complexity. We introduce additive complexity in general, present several properties and characterizations of words with bounded additive complexity, and show how results on additive complexity can be generalized to other areas of subword complexity theory.

Sr. Supervisor: David Muraki

Title:
Rossby Wave Propagation in the Tropics and Midlatitudes

Abstract:
Rossby waves are the slow atmospheric waves that propagate thousands of kilometres on
the timescale of days and are associated with weather. The small amplitude linear theory of
Rossby waves on the sphere goes back over two centuries to Laplace's Tidal Equations and
is today considered thoroughly understood. However,with a more realistic background flow
that includes both the tropical tradewinds and the midlatitude jetstream, the global wave
theory has not been fully established. To study this problem, this thesis uses the Rotating
Shallow Water (RSW) equations on the sphere as a model for Earth's atmosphere. The
spectrum of the RSW equations is numerically computed using a Galerkin method. It is
found that the Rossby spectrum of this global model consists of two parts that naturally
correspond respectively to local tropical and midlatitude theories.
The first part of the spectrum is the countably in?nite set of discrete eigenmodes with
arbitrarily small wavelength near the equator, consistent with the local tropical ?-plane
theory. These discrete modes however, achieve only a ?nite limiting wavelength in the
midlatitudes. To account for smaller scales in the midlatitudes, it is necessary to consider
the continuous spectrum that results from regular singularpoints in the RSW operator
arising from shear in the background flow. Theregular singular points correspond to critical
latitudes, which prevent wave propagation from the midlatitudes into the tropics.
The numerical results are complimented by small wavelength asymptotics of ray theory
and Wentzel-Kramers-Brillouin (WKB) analysis to gain an understanding of the localwavelength,
amplitude and group velocity for Rossby waves. Further quantitative understanding
of the continuous spectrum waves near the critical latitudes is achieved using the method
of Frobenius. Finally, the global understanding of Rossby waves presented in this thesis is
used to provide some explanation of the small number of Rossby modes found in long-term
climatological observations of the real atmosphere.

Title: Graph minor embeddings and quantum annealing
Abstract:
Quantum annealing is an algorithm that uses quantum information to solve discrete optimization problems, sometimes faster than any classical system.D-Wave Systems has developed hardware to solve quadratic boolean optimization problems (QUBOs) using quantum annealing, but the technology is limited by both the number of variables in the problem and the number of interactions between variables. By representing variables as vertices and interactions as edges, many of the difficulties in applying the quantum annealer can be thought of as embedding problems in graph theory.

We discuss two examples of this in detail. First, we describe how mapping a QUBO into D-Wave's architecture is an example of graph-minor embedding. We describe a new heuristic for minor embedding, which, in contrast with exact algorithms for minorembedding, is practical. Second, we describe a new generalization of tree-decompositions of graphs called G-decompositions and explain how they can be used to evaluate arbitrary QUBOs on the D-Wave hardware.