Combinatorics and Optimization

Permanent URI for this collection

https://uwspace.uwaterloo.ca/handle/10012/9928

This is the collection for the University of Waterloo's Department of Combinatorics and Optimization.

Research outputs are organized by type (eg. Master Thesis, Article, Conference Paper).

Waterloo faculty, students, and staff can contact us or visit the UWSpace guide to learn more about depositing their research.

Browse

Now showing 1 - 20 of 450

Theory and Results on Restarting Schemes for Accelerated First Order Methods
(University of Waterloo, 2024-09-10) Pavlovic, Viktor
Composite convex optimization problems are abundant in industry, and first order methods to solve them are growing in popularity as the size of variables reaches billions. Since the objective function could be possibly non-smooth, proximal gradient methods are one of the main tools for these problems. These methods benefit from acceleration, which uses the memory of past iterates to add momentum to the algorithms. Such methods have a O(1/k^2) convergence rate in terms of function value where k is the iteration number. Restarting algorithms has been seen to help speed up algorithms. O'Donoghue and Candes introduced adaptive restart strategies for accelerated first order methods which rely on easy to compute conditions, and indicate a large performance boost in terms of convergence. The restart works by resetting the momentum gained from acceleration. Their strategies in general are a heuristic, and there is no proof of convergence. In this thesis we show that restarting with the O'Donoghue and Candes condition improves the standard convergence rate in special cases. We consider the case of one-dimensional functions where we prove that the gradient based restart strategy from O'Donoghue and Candes improves the O(1/k^2) bound. We also study the restarting scheme applied to the method of alternating projections (MAP) for two closed, convex, and nonempty sets. It is shown in Chapter 6 that MAP falls into the convex composite paradigm and therefore acceleration can be applied. We study the case of MAP applied to two hyperplanes in arbitrary dimension. Furthermore we make observations as to why the restarts help, what makes a good restart condition, as well as what is needed to make progress in the general case.
Tubings of Rooted Trees
(University of Waterloo, 2024-09-05) Cantwell, Amelia
A tubing of a rooted tree is a broad term for a way to split up the tree into induced connected subtrees. They are useful for computing series expansion coefficients. This thesis discusses two different definitions of tubings, one which helps us understand Dyson- Schwinger equations, and the other which helps us understand the Magnus expansion. Chord diagrams are combinatorial objects that relate points on a circle. We can explicitly map rooted connected chord diagrams to tubings of rooted trees by a bijection, and we explore further combinatorial properties arising from this map. Furthermore, this thesis describes how re-rooting a tubed tree will change the chord diagram. We present an algorithm for finding the new chord diagram by switching some chords around. Finally, a different notion of tubings of rooted trees is introduced, which was originally developed by Mencattini and Quesney [27]. They defined two sub-types of tubings: vertical and horizontal which are used to find coefficients in the Magnus expansion. These two types of tubings have an interesting relationship when the forests are viewed as plane posets.
Tight Multi-Target Security for Key Encapsulation Mechanisms
(University of Waterloo, 2024-09-04) Glabush, Lewis
The use of symmetric encryption schemes requires that the communicating parties have access to a shared secret key. A key encapsulation mechanism (KEM) is a cryptographic tool for the secure establishment of such a key. The KEMs most commonly used at this time are vulnerable to adversaries with access to a large quantum computer. This project concerns KEMs that are resistant to all known quantum attacks, such as lattice-based schemes. A desirable property for any KEM is multi-target security, capturing the idea that security does not degrade below the targeted level as the number of users of a protocol or the amount of communication per user scales to a certain threshold. For schemes based on prime-order groups, multi-ciphertext security can be trivially reduced to singleciphertext security using self reducibility arguments, but these arguments are not available for lattice-based schemes. Indeed, one of the alternates in NIST’s post-quantum cryptography standardization project, FrodoKEM, was susceptible to simple attacks in the multi-target setting. The standard approach to building IND-CCA secure KEMs has been to start with an IND-CPA secure public key encryption scheme (PKE) and apply the Fujisaki-Okamoto transform (FO). In this paper, we introduce a new variant of the FO transform, called the salted FO transform (SFO) which adds a uniformly random salt to the generation of ciphertexts. We then show that the resulting KEM’s have much tighter security bounds compared to their generic counterparts. We then apply our results to FrodoKEM to resolve the aforementioned simple attacks.
Price-setting Problems and Matroid Bayesian Online Selection
(University of Waterloo, 2024-08-30) DeHaan, Ian
We study a class of Bayesian online selection problems with matroid constraints. Consider a seller who has several items they wish to sell, with the set of sold items being subject to some structural constraints, e.g., the set of sold items should be independent with respect to some matroid. Each item has an offer value drawn independently from a known distribution. In a known order, items arrive and drawn values are presented to the seller. If the seller chooses to sell the item, they gain the drawn value as revenue. Given distribution information for each item, the seller wishes to maximize their expected revenue by carefully choosing which offers to accept as they arrive. Such problems have been studied extensively when the seller's revenue is compared with the offline optimum, referred to as the "prophet". In this setting, a tight 2-competitive algorithm is known when the seller is limited to selling independent sets of a matroid [KW12]. We turn our attention to the online optimum, or "philosopher", and ask how well the seller can do with polynomial-time computation, compared to a seller with unlimited computation but with the same limited distribution information about offers. We show that when the underlying constraints are laminar and the arrival of buyers follows a natural "left-to-right" order, there is a polynomial-time approximation scheme for maximizing the seller's revenue. We also show that such a result is impossible for the related case when the underlying constraints correspond to a graphic matroid. In particular, it is PSPACE-hard to approximate the philosopher's expected revenue to some fixed constant α < 1; moreover, this cannot be alleviated by requirements on the arrival order in the case of graphic matroids. We also show similar hardness results for both transversal and cographic matroids. We then turn our attention to a related problem where the arrival order of items is unknown and uniformly random. In this setting, we show that there is a polynomial-time approximation scheme whenever the rank of the matroid is bounded above by a constant and all probabilities in the input are bounded below by a constant. We additionally examine the computational complexity of computing the prophet's expected revenue. We show that this problem is #P-hard, and give a fully polynomial-time randomized approximation scheme for the problem.
Contracts for Density and Packing Functions
(University of Waterloo, 2024-08-30) Skitsko, Jacob
We study contracts for combinatorial problems in multi-agent settings. In this problem, a principal designs a contract with several agents, whose actions the principal is unable to observe. The principal is able to see only the outcome of the agents' collective actions. All agents that decided to exert effort incur costs, and so naturally all agents expect a fraction of the principal's reward as a compensation. The principal needs to decide what fraction of their reward to give to each agent so that the principal's expected utility is maximized. One of our focuses is on the case when the principal's reward function is supermodular and is based on some graph. Recently, Deo-Campo Vuong et al. showed that for this problem it is impossible to provide any finite multiplicative approximation or additive FPTAS unless P=NP. On a positive note, Deo-Campo Vuong et al. provided an additive PTAS for the case when all agents have the same cost. Deo-Campo Vuong et al. asked whether an additive PTAS can be obtained for the general case, i.e for the case when agents potentially have different costs. In this thesis, we answer this open question in positive. Additionally, we provide multiplicative approximation algorithms for functions that are based on hypergraphs and encode packing constraints. This family of functions provides a generalization for XOS functions.
Control over the KKR bijection with respect to the nesting structure on rigged configurations and a CSP instance involving Motzkin numbers
(University of Waterloo, 2024-08-27) Chan, William
There are two disjoint main projects that this thesis covers. The Motzkin numbers are a sort of “re- laxed version” of the Catalan numbers. For example, Catalan numbers count perfect non-crossing matchings, while Motzkin numbers count not necessarily perfect non-crossing matchings. The first project deals with instances of the cyclic sieving phenomenon involving Motzkin numbers and their standard q−analogue. We also show that the standard q−analogue for Motzkin numbers satisfy a similar generating series interpretation to that of the q−Catalan numbers. The second project deals with understanding the Kerov-Kirillov-Reshetikhin (KKR) bijection between semistandard tableaux and rigged configurations with a particular emphasis on the standard case. In partic- ular, we understand inducing perturbations on the corresponding rigged configuration via direct operations on the tableau. We develop a technique to take a standard tableau T, and output a new standard tableau T′ which has the same corresponding rigged configuration up to a rigging on any desired row of the first rigged partition. We also develop an alternate technique to Kuniba, Okado, Sakamoto, Takagi, and Yamada that “unwraps” the natural nesting structure on rigged configurations. The primary operation from which all the above follows from is “raise” which we introduce and give various combinatorial models for. The operation raise induces a very simple, controlled perturbation on the corresponding rigged configuration. Our results are formulated in terms of paths or (classically) highest weight elements of tensor products of Kirillov-Reshetikhin crystals.
Euclidean Distance Matrix Correction with a Single Corrupted Element
(University of Waterloo, 2024-08-27) Tina Chenrui, Xu
In this thesis, we study the problem of correcting the error from a noisy Euclidean distance matrix (EDM). An EDM is a matrix where elements are squared distance between points in R^d. We consider the special case where only one of the distance is corrupted. We develop efficient algorithms to solve this problem, initially assuming that the points are in general position, and solve the problem using three different types of facial reduction: exposing vector, facial vectors, and Gale transform. Furthermore, we investigate yielding elements of an EDM and develop an algorithm for identifying one small principal submatrix with the embedding dimension d when many of the points are in a linear manifold of dimension smaller than d, allowing us to handle a more general problem. We present numerical experiments implemented in MATLAB, demonstrating the effectiveness of our solutions.
Non-Generic Analytic Combinatorics in Several Variables and Lattice Path Asymptotics
(University of Waterloo, 2024-08-27) Kroitor, Alexander
Finding and analyzing generating functions is a classic and powerful way of studying combinatorial structures. While generating functions are a priori purely formal objects, there is a rich theory treating them as complex-analytic functions. This is the field of analytic combinatorics, which exploits classical results in complex and harmonic analysis to find asymptotics of coefficient sequences of generating functions. More recently, the field of analytic combinatorics in several variables has been developed to study multivariate generating functions, which are amenable to multivariate analytic results. When dealing with multivariate asymptotics we first pick a direction vector. To find asymptotics using analytic combinatorics, one typically uses the Cauchy integral formula to write the underlying sequence being studied as a complex integral, then uses residue computations to reduce to a so-called Fourier-Laplace integral. When the direction vector chosen is generic, the Fourier-Laplace integral being studied is well-behaved and asymptotics can be computed. When the direction vector chosen is non-generic, the Fourier-Laplace integral has singular amplitude, and asymptotics are harder to compute. This thesis studies singular Fourier-Laplace integrals and their applications to combinatorics. Determining asymptotics for the number of lattice walks restricted to certain regions is one of the particular successes of analytic combinatorics in several variables. In particular, Melczer and Mishna determined asymptotics for the number of walks in an orthant whose set of steps is a subset of { ±1, 0 }^d \ { 0 } and is symmetric over every axis. Melczer and Wilson later determined asymptotics for lattice path models whose set of steps is a subset of { ±1, 0 }^d \ { 0 } and is symmetric over all but one axis, except when the vector sum of all the steps is 0. Here we determine asymptotics in the zero sum case using asymptotics of singular Fourier-Laplace integrals. We additionally study asymptotics of lattice path models restricted to Weyl chambers, before giving some generalizations of asymptotics of singular Fourier-Laplace integrals.
Fault-tolerant Preparation of Distant Logical Bell Pair - with application in the Magic Square Game
(University of Waterloo, 2024-08-23) Liu, Andy Zeyi
Quantum entanglement facilitates nonlocal correlations that defy classical physics, forming the basis for quantum technologies, including quantum computation and communication. Nonlocal games exemplify this power, where entangled players achieve outcomes unattainable by classical means. This thesis focuses on optimizing the preparation of high-fidelity logical Bell pairs in the context of the fault-tolerant magic square game, seeking to minimize Bell pair(ebit) consumption while maintaining a low logical error rate. In this thesis, we introduce a novel approach leveraging an interface circuit and entanglement purification protocol (EPP) to translate states between physical and logical qubits and purify noisy logical ebits. This method significantly reduces the number of initial ebits needed compared to conventional strategies. Our analytical and numerical analyses, particularly for the [[7k,1,3k]] concatenated Steane code, demonstrate substantial (actually, exponential) ebit savings and higher noise threshold. Analytical lower bounds for local noise threshold of 4.70 × 10−4 and initial ebit infidelity threshold of 18.3% are obtained. Additionally, we construct an analogous interface for the surface code through lattice surgery, offering further improvements in fault tolerance and compatibility with current quantum hardware. Our framework is adaptable to various quantum error-correcting codes (QECCs) and experimental platforms. We hope our protocol will not only enhance understanding of fault-tolerant nonlocal games, but also spark further exploration of interfacing between different QECCs, promoting the development of modular quantum architectures and advancing quantum internet.
Degrees of P -Grothendieck polynomials and regularity of Pfaffian varieties
(University of Waterloo, 2024-08-23) St.Denis, Matthew
We prove a formula for the degrees of Ikeda and Naruse’s P -Grothendieck polynomials using combinatorics of shifted tableaux. We show this formula can be used in conjunction with results of Hamaker, Marberg, and Pawlowski to obtain an upper bound on the Castelnuovo–Mumford regularity of certain Pfaffian varieties known as vexillary skew-symmetric matrix Schubert varieties. Similar combinatorics additionally yields a new formula for the degree of Grassmannian Grothendieck polynomials and the regularity of Grassmannian matrix Schubert varieties, complementing a 2021 formula of Rajchgot, Ren, Robichaux, St. Dizier, and Weigandt.
Arboricity and transversal problems on bounded degree graphs
(University of Waterloo, 2024-08-19) Wdowinski, Ronen
In this thesis, we investigate arboricity and transversal problems on graphs in a bounded degree setting. We pay particular attention to problems involving both the maximum degree and maximum density of the graphs. The first topic is bounded degree arboricity. The arboricity of a multigraph $G$ is the minimum number of forests required to cover its edge set. It is well understood through a theorem of Nash-Williams. For the problem of bounded degree arboricity, we seek to cover the edge set of a multigraph $G$ by the minimum number of forests such that every vertex $v$ has maximum degree at most $f(v)$ in every forest, for some fixed weight function $f : V(G) \rightarrow \mathbb{Z}_{\ge 2}$. The case $f = 2$ is referred to as linear arboricity. The Linear Arboricity Conjecture, due to Akiyama, Exoo, and Harary, asserts that the linear arboricity of a simple graph $G$ with maximum degree $\Delta$ is at most $\lceil (\Delta+1)/2 \rceil$. Using tools from orientations of multigraphs, we prove that the Linear Arboricity Conjecture holds for multigraphs whose maximum degree is sufficiently large compared to a certain maximum density. This improves on previous results of this type, and moreover our methods extend to give a general upper bound on the bounded degree arboricity of multigraphs, as a maximum of a weighted maximum degree and maximum density of the multigraph. In addition, we disprove a conjecture of Truszczy\'nski which proposes a more precise upper bound on the bounded degree arboricity of multigraphs, but we also show that the conjecture does hold for simple graphs with sufficiently large girth, and that it holds for all simple graphs asymptotically. The second topic in this thesis is independent transversals in bounded degree graphs. Given a graph $G$ and a partition $\mathcal{P} = \{V_1, \ldots, V_n\}$ of its vertex set, an independent transversal is a transversal of $\mathcal{P}$ that is independent in $G$. Haxell proved that there exists an independent transversal when $G$ has maximum degree $\Delta$ and $|V_i| \ge 2\Delta$ for every $i$, and this condition has been shown to be best possible by Szab\'o and Tardos. Wanless and Wood proved the existence of an independent transversal when the maximum class average degree (a kind of maximum density) of $G, \mathcal{P}$ is $D$ and $|V_i| \ge 4D$ for every $i$, and this condition has been shown to be asymptotically best possible by Groenland, Kaiser, Treffers, and Wales. Using topological methods, we find an interpolation between these two sufficient conditions, and moreover we give a construction showing that our result is best possible. The method for our tight construction, based on a simple lemma, is then further explored. We use our method to streamline tight constructions for Haxell's theorem, and we prove that our method in fact yields all possible extremal constructions. We also use it to give more streamlined counterexamples to a list coloring conjecture of Reed. Then we adapt the construction method to the setting of full rainbow matchings of multi-hypergraphs, which are independent transversals in their line graphs. Aharoni, Berger, and Meshulam proved that there exists a full rainbow matching in an $r$-uniform multigraph $G$ with maximum degree $\Delta$ when every edge class has size $|E_i| \ge r\Delta$. We use our method to give tight constructions for this theorem. We also describe counterexamples to a color degree generalization of Galvin's Theorem on list edge-coloring bipartite multigraphs. Finally, we describe how our method applies to independent transversals in uniform hypergraphs and other related settings.
On K-theoretic polynomials and the chromatic symmetric function
(University of Waterloo, 2024-08-16) Pierson, Laura
This thesis explores various problems related to polynomials from combinatorial K-theory and/or to the chromatic symmetric function. We prove four main results: 1. Two alternating sum formulas involving K-theoretic polynomials, conjectured by Monical, Pechenik, and Searles (2021). 2. The fact that certain properties of a graph can be recovered from its Kromatic symmetric function. 3. A power sum expansion for the Kromatic symmetric function, which we show has integer coefficients. 4. Formulas for certain pieces of the chromatic symmetric homology for star graphs. The organization is as follows: In Chapter 1, we introduce background on symmetric functions and K-theory. The basic idea of K-theory is to deform cohomology rings by introducing an extra parameter β, often set to -1. In Chapter 2, we prove an alternating sum conjecture of Monical, Pechenik, and Searles (2021) concerning four different sets of K-theoretic polynomials: the Lascoux atoms, the kaons, the quasiLascoux polynomials, and the glide polynomials. Monical, Pechenik, and Searles (2021) proved that the coefficients in the kaon expansion of the Lascoux atoms and the coefficients in the glide expansion of the quasiLascoux polynomials are monomials in β. We prove their conjecture that for β = -1, the sum of the coefficients in each of these expansions is always either 0 or 1. In Chapter 3, we give background on the chromatic symmetric function (introduced by Stanley (1995)), and its K-analogue, the Kromatic symmetric function (introduced by Crew, Pechenik and Spirkl (2023)). A proper coloring of a graph is a way of assigning a color to each vertex such that adjacent vertices always receive different colors. The chromatic symmetric function is computed by assigning a variable to each color then summing the monomials for all proper colorings of G, where in each monomial, the exponent of each variable is the number of times that color is used. The Kromatic symmetric function is defined similarly except that the monomials correspond to proper set colorings, meaning each vertex is assigned a nonempty set of colors such that adjacent vertices have non-overlapping color sets. In Chapter 4, we study a question posed by Crew, Pechenik, and Spirkl (2023) about how much information about a graph can be recovered from its Kromatic symmetric function. It is known to be a stronger graph invariant than the chromatic symmetric function, and we conjecture that it is in fact a complete invariant that distinguishes all graphs. As evidence toward this conjecture, we prove that the number of copies in G of certain induced subgraphs can be recovered from its Kromatic symmetric function. In Chapter 5, we give a formula for the expansion of the Kromatic symmetric function using a K-analogue for the power sum basis of the ring of symmetric functions. We show that this expansion has all integer coefficients, as conjectured by Crew, Pechenik, and Spirkl (2023). In Chapter 6, we study the chromatic symmetric homology, which is a categorification of the chromatic symmetric function introduced by Sazdanovic and Yip (2018). We compute the multiplicity of certain Specht modules in in the case where G is a star graph, confirming and extending some conjectures of Chandler, Sazdanovic, Stella, and Yip (2023).
Foreshadowing the Grid Theorem for Induced Subgraphs
(University of Waterloo, 2024-08-07) Hajebi, Sepehr
We prove several dichotomy theorems toward a complete description of the unavoidable induced subgraphs of graphs with large treewidth. This is motivated by the Grid Theorem of Robertson and Seymour (1986) which achieves the same goal for minors (and subgraphs). Given a graph class C, we say that C is clean if the only induced subgraph obstructions to bounded treewidth in C are the basic ones: complete graphs, complete bipartite graphs, subdivided walls and the line graphs of the subdivided walls. The analog of the Grid Theorem for induced subgraphs (still out of reach) is then observed to be equivalent to a characterization of all hereditary classes that are clean. We characterize all clean classes that are defined by finitely many excluded induced subgraphs. Specifically, we identify a family of “non-basic” obstructions which, in this scenario, litmus-test the clean classes against the non-clean ones. The analogous characterization remains elusive in the case of infinitely many forbidden induced subgraphs. Among the infinite sets of graphs whose exclusion is known to result in a non-clean class, the following four appear to expose a distinctive gap in our understanding of cleanness: (1) Graphs which are the union of three cycles, all sharing a vertex and otherwise pairwise vertex-disjoint. (2) Graphs which are the union of two vertex-disjoint cycles. (3) Graphs consisting of two non-adjacent vertices with three pairwise internally disjoint paths between them, known as thetas. (4) Cycles with an even number of vertices (at least four), known as even holes. For i = 1, 2, 3, 4, let Ci be the class obtained by excluding the ith set above. We prove a full “grid-type theorem” for each of C1 and C2. Both results extend to an arbitrary number of excluded cycles (instead of “three” and “two”) of lower bounded lengths. In C3 and C4, we characterize the “local” structure of graphs with large treewidth. Explicitly, given a graph H, we prove the following: (a) Every (theta, K3)-free graph of large enough treewidth has an induced subgraph isomorphic to H, if and only if H is a K3-free chordal graph (that is, a forest). (b) Every (even hole K4)-free graph of large enough treewidth has an induced subgraph isomorphic to H, if and only if H is a K4-free chordal graph. We generalize both (a) and (b) to the “right” class of Kt-free graphs for all t. We also derive, from a very special case of (b), one of the two conjectures of Sintiari and Trotignon on even-hole-free graphs of large treewidth.
Some Applications of Combinatorial Hopf Algebras to Integro-Differential Equations and Symmetric Function Identities
(University of Waterloo, 2024-07-09) Olson-Harris, Nicholas
Hopf algebras built from combinatorial objects have found application both within combinatorics and, following the work of Connes and Kreimer, in quantum field theory. Despite the apparent gulf between these areas, the types of Hopf algebras that arise are very similar. We use Hopf algebra techniques to solve two problems, one coming from quantum field theory and one from algebraic combinatorics. (1) Dyson–Schwinger equations are a formulation of the equations of motion of quantum field theory. From a mathematical perspective they are integro-differential equations which have a recursive, tree-like structure. In some cases, these equations are known to have solutions which can be written as combinatorial expansions over connected chord diagrams. We give a new expansion in terms of rooted trees equipped with a kind of decomposition we call a binary tubing. This is similar to the chord diagram expansion, but holds in greater generality, including to systems of Dyson–Schwinger equations and to Dyson–Schwinger equations in which insertion places are distinguished by different variables in the Mellin transform. Moreover we prove these results as a direct application of a purely Hopf-algebraic theorem characterizing maps from the Connes–Kreimer Hopf algebra of rooted trees (and variants thereof) to the Hopf algebra of univariate polynomials which arise from the universal property of the former. (2) A pair of skew Ferrers shapes are said to be skew-equivalent if they admit the same number of semistandard Young tableaux of each weight, or in other words if the skew Schur functions they define are equal. McNamara and van Willigenburg conjectured necessary and sufficient combinatorial conditions for this to happen but were unable to prove either direction in complete generality. Using Hopf-algebraic techniques building on a partial result of Yeats, we prove sufficiency.
Chromatic Number of Random Signed Graphs
(University of Waterloo, 2024-05-03) Yuan, Dao Chen
We naturally extend Bollobas's classical method and result about the chromatic number of random graphs chi(G(n,p)) ~ n/log_b(n) (for p constant, b=1/(1-p)) to the chromatic number of random signed graphs to obtain chi(G(n,p,q)) ~ n/log_b(n) (for p constant, b=1/(1-p), q=o(1)). We also give a sufficient bound on q under which a.a.s. the chromatic number of G(n,p,q) is unchanged before and after adding negative edges.
Routing, Scheduling, and Sorting in Consolidated Networks
(University of Waterloo, 2024-04-25) Van Dyk, Madison
Modern parcel logistic networks are designed to ship demand between given origin, destination pairs of nodes in an underlying directed network. Efficiency dictates that volume needs to be consolidated at intermediate nodes in typical hub-and-spoke fashion. In practice, such consolidation requires tracking packages in both space and time (temporal network design), as well as parcel sortation. In the first half of the thesis, we study solution methods for temporal problems arising in consolidated networks. While many time-dependent network design problems can be formulated as time-indexed formulations, the size of these formulations depends on the discretization of the time horizon and can become prohibitively large. The recently-developed dynamic discretization discovery (DDD) method allows many time-dependent problems to become more tractable by iteratively solving instances of the problem on smaller networks where each node has its own discrete set of departure times. There are two design elements of existing DDD algorithms that make it problematic for use in region-based hub-and-spoke networks. First, in each iteration, all arcs departing a common node share the same set of departure times. This causes DDD to be ineffective for solving problems where all near-optimal solutions require many distinct departure times at the majority of the high-degree nodes in the network, an aspect characteristic of region-based networks. A second challenge is handling static storage constraints without leading to a weak relaxation in each iteration. To mitigate these limitations, an arc-based DDD framework is proposed in Chapter 3, where departure times are determined at the arc level instead of the node level. We apply this arc-based DDD method to instances of the service network design problem (SND). We show that an arc-based approach is particularly advantageous when instances arise from region-based networks, and when candidate paths are fixed in the base graph for each commodity. Moreover, our algorithm builds upon the existing DDD framework and achieves these improvements with only benign modifications to the original implementation. Additionally, Chapter 4 introduces bounds on additional storage required in each iteration, expanding the applicability of DDD to problems with bounded node storage, such as the universal packet routing problem. Our arguments rely solely on the structure of the standard map, μ, from the original formulation to the smaller relaxed formulations. In order to maintain consistent operations, some models stipulate that the implemented transportation schedule must be repeated each day. In Chapter 5 we present a DDD model for solving a version of SND with cyclic constraints. We show that these cyclic constraints require new conditions on the time discretization at each node, leading to larger partial networks. We then highlight challenges in reducing the size of partial networks as they grow over each iteration of DDD. We demonstrate that certain policies for removing departure times in each iteration can cause the iterations in DDD to repeat, preventing termination. In the second half of this thesis, we study parcel sortation, an aspect of routing that has previously been left unaddressed from a theory perspective. Warehouses have limited sort points, the physical devices tasked with handling packages destined for a particular downstream warehouse. We propose a mathematical model for the physical requirements, and limitations of parcel sortation. We then show that it is NP-hard to determine whether a feasible sortation plan exists. We consider two natural objectives: minimizing the maximum number of sort points required at a warehouse, and minimizing the total number of sort points required in the network. In Chapter 6, we consider the problem of minimizing the maximum number of sort points required at a warehouse. We discuss several settings, where (near-)optimality of a given sortation instance can be determined efficiently. The algorithms we propose are fast and build on combinatorial witness set type lower bounds that are reminiscent and extend those used in earlier work on degree-bounded spanning trees and arborescences. In Chapter 7, we present algorithms for minimizing the total number of sort points required in a network. In contrast to the min-degree setting, it is not known if this min-cardinality setting is NP-hard. In progress towards answering this question, we present fast combinatorial algorithms for solving in-tree, out-tree, and spider instances. Our algorithms are based on reduction, decomposition, and uncrossing techniques that simplify instances.
Analytic Methods and Combinatorial Plants
(University of Waterloo, 2024-04-08) Chizewer, Jeremy
Combinatorial structures have broad applications in computer science, from error-correcting codes to matrix multiplication. Many analytic tools have been developed for studying these structures. In this thesis, we examine three applications of these tools to problems in combinatorics. By coincidence, each problem involves a combinatorial structure named for a plant--AVL trees, cactus graphs, and sunflowers--which we refer to collectively as combinatorial plants. In our first result, we use a novel decomposition to create a succinct encoding for tree classes satisfying certain properties, extending results of Munro, Nicholson, Benkner, and Wild. This has applications to the study of data structures in computer science, and our encoding supports a wide range of operations in constant time. To analyze our encoding, we derive asymptotics for the information-theoretic lower bound on the number of bits needed to store these trees. Our method characterizes the exponential growth for the counting sequence of combinatorial classes whose generating functions satisfy certain functional equations, and may be of independent interest. Our analysis applies to AVL trees (a commonly studied self-balancing binary search tree in computer science) as a special case, and we show that about $0.938$ bits per node are necessary and sufficient to encode AVL trees. Next, we study the hat guessing game on graphs. In this game, a player is placed on each vertex $v$ of a graph $G$ and assigned a colored hat from $h(v)$ possible colors. Each player makes a deterministic guess on their hat color based on the colors assigned to the players on neighboring vertices, and the players win if at least one player correctly guesses his assigned color. If there exists a strategy that ensures at least one player guesses correctly for every possible assignment of colors, the game defined by $\langle G,h\rangle$ is called winning. The hat guessing number of $G$ is the largest integer $q$ so that if $h(v)=q$ for all $v\in G$ then $\langle G,h\rangle$ is winning. We determine whether $\langle G,h\rangle $ is winning for any $h$ whenever $G$ is a cycle, resolving a conjecture of Kokhas and Latyshev in the affirmative and extending it. We then use this result to determine the hat guessing number of every cactus graph, in which every pair of cycles shares at most one vertex. Finally, we study the sunflower problem. A sunflower with $r$ petals is a collection of $r$ sets over a ground set $X$ such that every element in $X$ is in no set, every set, or exactly one set. Erd\H{o}s and Rado~\cite{er} showed that a family of sets of size $n$ contains a sunflower if there are more than $n!(r-1)^n$ sets in the family. Alweiss et al.~\cite{alwz}, and subsequently Rao~\cite{rao} and Bell et al.~\cite{bcw}, improved this bound to $(O(r \log(n))^n$. We study the case where the pairwise intersections of the set family are restricted. In particular, we improve the best-known bound for set families when the size of the pairwise intersections of any two sets is in a set $L$. We also present a new bound for the special case when the set $L$ is the nonnegative integers less than or equal to $d$, using techniques of Alweiss et al.~\cite{alwz}.
Graph-Theoretic Techniques for Optimizing NISQ Algorithms
(University of Waterloo, 2024-02-15) Jena, Andrew
Entering the NISQ era, the search for useful yet simple quantum algorithms is perhaps of more importance now than it may ever be in the future. In place of quantum walks, the quantum Fourier transform, and asymptotic results about far-term advantages of quantum computation, the real-world applications of today involve nitty-gritty details and optimizations which make the most use of our limited resources. These priorities pervade the research presented in this thesis, which focuses on combinatorial techniques for optimizing NISQ algorithms. With variational algorithms directing the discussion, we investigate methods for reducing Hamiltonians, reducing measurement errors, and reducing entangling gates. All three of these reductions bring us ever closer to demonstrating the utility of quantum devices, by improving some of the major bottlenecks of the NISQ era, and all of them do so while rarely ever leaving the combinatorial framework provided by stabilizer states. The qubit tapering approach to Hamiltonian simplification which we present was developed independently of the work by Bravyi et al., who discovered how to reduce qubit counts by parallelizing the computation of the ground state. The measurement scheme we describe, AEQuO, is built upon years of research and dozens of articles detailing, comparing, and contrasting a plethora of schemes. The circuit optimization technique we introduce answers a question posed by Adcock et al., and our ideas and proofs are fundamentally grounded in the literature of isotropic systems and the graph-based results which have followed from it.
Formalizing the Excluded Minor Characterization of Binary Matroids in the Lean Theorem Prover
(University of Waterloo, 2024-01-23) Gusakov, Alena
A matroid is a mathematical object that generalizes the notion of linear independence of a set of vectors to an abstract independence of sets, with applications to optimization, linear algebra, graph theory, and algebraic geometry. Matroid theorists are often concerned with representations of matroids over fields. Tutte's seminal theorem proven in 1958 characterizes matroids representable over GF(2) by noncontainment of U2,4 as a matroid minor. In this thesis, we document a formalization of the theorem and its proof in the Lean Theorem Prover, building on its community-built mathematics library, mathlib.
Implementing the Castryck-Decru attack on SIDH with general primes
(University of Waterloo, 2024-01-09) Laflamme, Jeanne
With the rapid progress of quantum computers in recent years, efforts have been made to standardize new public-key cryptographic protocols which would be secure against them. One of the schemes in contention was Supersingular Isogeny Diffie-Hellman (SIDH). This scheme relied on the assumed hardness of the isogeny problem on supersingular elliptic curves. However, in the SIDH protocol extra information on the secret isogenies is transmitted. In July 2022, Castryck and Decru found a way to exploit this information to completely break the scheme. They gave an implementation of their attack which allows to recover Bob’s secret key in a few seconds on a laptop. Usually, Alice and Bob’s secret isogenies are taken to have degree 2^a and 3^b respectively. This thesis gives a more general implementation of the attack in Magma which works even if Alice and Bob’s secret isogenies have degrees lA^a and lB^b for more general primes lA and lB.

Browse

Recent Submissions