Combinatorics and Optimization

Permanent URI for this collectionhttps://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 453

2-crossing critical graphs with a V8 minor
(University of Waterloo, 2012-01-17T20:51:50Z) Austin, Beth Ann
The crossing number of a graph is the minimum number of pairwise crossings of edges among all planar drawings of the graph. A graph G is k-crossing critical if it has crossing number k and any proper subgraph of G has a crossing number less than k. The set of 1-crossing critical graphs is is determined by Kuratowski’s Theorem to be {K5, K3,3}. Work has been done to approach the problem of classifying all 2-crossing critical graphs. The graph V2n is a cycle on 2n vertices with n intersecting chords. The only remaining graphs to find in the classification of 2-crossing critical graphs are those that are 3-connected with a V8 minor but no V10 minor. This paper seeks to fill some of this gap by defining and completely describing a class of graphs called fully covered. In addition, we examine other ways in which graphs may be 2-crossing critical. This discussion classifies all known examples of 3-connected, 2-crossing critical graphs with a V8 minor but no V10 minor.
5-Choosability of Planar-plus-two-edge Graphs
(University of Waterloo, 2018-01-02) Mahmoud, Amena
We prove that graphs that can be made planar by deleting two edges are 5-choosable. To arrive at this, first we prove an extension of a theorem of Thomassen. Second, we prove an extension of a theorem Postle and Thomas. The difference between our extensions and the theorems of Thomassen and of Postle and Thomas is that we allow the graph to contain an inner 4-list vertex. We also use a colouring technique from two papers by Dvořák, Lidický and Škrekovski, and independently by Compos and Havet.
Action of degenerate Bethe operators on representations of the symmetric group
(University of Waterloo, 2018-05-24) Rahman, Sifat
Degenerate Bethe operators are elements defined by explicit sums in the center of the group algebra of the symmetric group. They are useful on account of their relation to the Gelfand-Zetlin algebra and the Young-Jucys-Murphy elements, both of which are important objects in the Okounkov-Vershik approach to the representation theory of the symmetric group. We examine all of these results over the course of the thesis. Degenerate Bethe operators are a new, albeit promising, topic. Therefore, we include proofs for previously-unproven basic aspects of their theory. The primary contribution of this thesis, however, is the computation of eigenvalues and eigenvectors of all the degenerate Bethe operators in sizes 4 and 5, as well as many in size 6. For each partition $\bld{\lambda} \vdash k$ we compute the operators $B_{\ell j}$, where $\ell + j \leq k$, and give the eigenvalues and their corresponding eigenvectors in terms of standard Young tableaux of shape $\bld{\lambda}$. The number of terms in the degenerate Bethe operators grows very rapidly so we used a program written in the computer algebra system \texttt{SAGE} to compute the eigenvalue-eigenvector pair data. From this data, we observed a number of patterns that we have formalized and proven, although others remain conjectural. All of the data computed is collected in an appendix to this thesis.
Acyclic Colouring of Graphs on Surfaces
(University of Waterloo, 2018-09-04) Redlin, Shayla
An acyclic k-colouring of a graph G is a proper k-colouring of G with no bichromatic cycles. In 1979, Borodin proved that planar graphs are acyclically 5-colourable, an analog of the Four Colour Theorem. Kawarabayashi and Mohar proved in 2010 that "locally" planar graphs are acyclically 7-colourable, an analog of Thomassen's result that "locally" planar graphs are 5-colourable. We say that a graph G is critical for (acyclic) k-colouring if G is not (acyclically) k-colourable, but all proper subgraphs of G are. In 1997, Thomassen proved that for every k >= 5 and every surface S, there are only finitely many graphs that embed in S that are critical for k-colouring. Here we prove the analogous result that for each k >= 12 and each surface S, there are finitely many graphs embeddable on S that are critical for acyclic k-colouring. This result implies that there exists a linear time algorithm that, given a surface S and large enough k, decides whether a graph embedded in S is acyclically k-colourable.
ADMM for SDP Relaxation of GP
(University of Waterloo, 2016-08-30) Sun, Hao
We consider the problem of partitioning the set of nodes of a graph G into k sets of given sizes in order to minimize the cut obtained after removing the k-th set. This is a variant of the well-known vertex separator problem that has applications in e.g., numerical linear algebra. This problem is well studied and there are many lower bounds such as: the standard eigenvalue bound; projected eigenvalue bounds using both the adjacency matrix and the Laplacian; quadratic programming (QP) bounds derived from imitating the (QP) bounds for the quadratic assignment problem; and semidefinite programming (SDP) bounds. For the quadratic assignment problem, a recent paper of [8] had great success from applying the ADMM (altenating direction method of multipliers) to the SDP relaxation. We consider the SDP relaxation of the vertex separator problem and the application of the ADMM method in solving the SDP. The main advantage of the ADMM method is that optimizing over the set of doubly non-negative matrices is about as difficult as optimizing over the set of positive semidefinite matrices. Enforcing the non-negativity constraint gives us a clear improvement in the quality of bounds obtained. We implement both a high rank and a nonconvex low rank ADMM method, where the difference is the choice of rank of the projection onto the semidefinite cone. As for the quadratic assignment problem, though there is no theoretical convergence guarantee, the nonconvex approach always converges to a feasible solution in practice.
Algebraic Analysis of Vertex-Distinguishing Edge-Colorings
(University of Waterloo, 2006) Clark, David
Vertex-distinguishing edge-colorings (vdec colorings) are a restriction of proper edge-colorings. These special colorings require that the sets of edge colors incident to every vertex be distinct. This is a relatively new field of study. We present a survey of known results concerning vdec colorings. We also define a new matrix which may be used to study vdec colorings, and examine its properties. We find several bounds on the eigenvalues of this matrix, as well as results concerning its determinant, and other properties. We finish by examining related topics and open problems.
Algebraic and combinatorial aspects of incidence groups and linear system non-local games arising from graphs
(University of Waterloo, 2019-06-06) Paddock, Connor
To every linear binary-constraint system (LinBCS) non-local game, there is an associated algebraic object called the solution group. Cleve, Liu, and Slofstra showed that a LinBCS game has a perfect quantum strategy if and only if an element, denoted by $J$, is non-trivial in this group. In this work, we restrict to the set of graph-LinBCS games, which arise from $\mathbb{Z}_2$-linear systems $Ax=b$, where $A$ is the incidence matrix of a connected graph, and $b$ is a (non-proper) vertex $2$-colouring. In this context, Arkhipov's theorem states that the corresponding graph-LinBCS game has a perfect quantum strategy, and no perfect classical strategy, if and only if the graph is non-planar and the $2$-colouring $b$ has odd parity. In addition to efficient methods for detecting quantum and classical strategies for these games, we show that computing the classical value, a problem that is NP-hard for general LinBCS games can be done efficiently. In this work, we describe a graph-LinBCS game by a $2$-coloured graph and call the corresponding solution group a graph incidence group. As a consequence of the Robertson-Seymour theorem, we show that every quotient-closed property of a graph incidence group can be expressed by a finite set of forbidden graph minors. Using this result, we recover one direction of Arkhipov's theorem and derive the forbidden graph minors for the graph incidence group properties: finiteness, and abelianness. Lastly, using the representation theory of the graph incidence group, we discuss how our graph minor criteria can be used to deduce information about the perfect strategies for graph-LinBCS games.
Algebraic Approach to Quantum Isomorphisms
(University of Waterloo, 2024-09-24) Sobchuk, Mariia
In very brief, this thesis is a study of quantum isomorphisms. We have started with two pairs of quantum isomorphic graphs and looked for generalizations of those. We have learned that those two pairs of graphs are related by Godsil-McKay switching and one of the graphs is an orthogonality graph of lines in a root system. These two observations lead to research in two directions. First, since quantum isomorphisms preserve coherent algebras, we studied a question of when Godsil-McKay switching preserved coherent algebras. In this way, non isomorphic graphs related by Godsil-McKay switching with isomorphic coherent algebras are candidates to being quantum isomorphic and non isomorphic. Second, while it was known that one of the graphs in a pair was an orthogonality graphs of the lines in a root system $E_8,$ we showed that a graph from another pair is also an orthogonality graph of the lines in a root system $F_4.$ We have studied orthogonality graphs of lines in root systems $B_{2^d},C_{2^d},D_{2^d}$ and showed that they have quantum symmetry. Finally, we have touched upon structures of quantum permutations, relationships between fractional and quantum isomorphisms as well as connection to quantum independence and chromatic numbers.
Algebraic Aspects of Multi-Particle Quantum Walks
(University of Waterloo, 2012-12-04T21:00:42Z) Smith, Jamie
A continuous time quantum walk consists of a particle moving among the vertices of a graph G. Its movement is governed by the structure of the graph. More formally, the adjacency matrix A is the Hamiltonian that determines the movement of our particle. Quantum walks have found a number of algorithmic applications, including unstructured search, element distinctness and Boolean formula evaluation. We will examine the properties of periodicity and state transfer. In particular, we will prove a result of the author along with Godsil, Kirkland and Severini, which states that pretty good state transfer occurs in a path of length n if and only if the n+1 is a power of two, a prime, or twice a prime. We will then examine the property of strong cospectrality, a necessary condition for pretty good state transfer from u to v. We will then consider quantum walks involving more than one particle. In addition to moving around the graph, these particles interact when they encounter one another. Varying the nature of the interaction term gives rise to a range of different behaviours. We will introduce two graph invariants, one using a continuous-time multi-particle quantum walk, and the other using a discrete-time quantum walk. Using cellular algebras, we will prove several results which characterize the strength of these two graph invariants. Let A be an association scheme of n × n matrices. Then, any element of A can act on the space of n × n matrices by left multiplication, right multiplication, and Schur multiplication. The set containing these three linear mappings for all elements of A generates an algebra. This is an example of a Jaeger algebra. Although these algebras were initially developed by Francois Jaeger in the context of spin models and knot invariants, they prove to be useful in describing multi-particle walks as well. We will focus on triply-regular association schemes, proving several new results regarding the representation of their Jaeger algebras. As an example, we present the simple modules of a Jaeger algebra for the 4-cube.
Algebraic Methods and Monotone Hurwitz Numbers
(University of Waterloo, 2012-09-21T15:43:44Z) Guay-Paquet, Mathieu
We develop algebraic methods to solve join-cut equations, which are partial differential equations that arise in the study of permutation factorizations. Using these techniques, we give a detailed study of the recently introduced monotone Hurwitz numbers, which count factorizations of a given permutation into a fixed number of transpositions, subject to some technical conditions known as transitivity and monotonicity. Part of the interest in monotone Hurwitz numbers comes from the fact that they have been identified as the coefficients in a certain asymptotic expansion related to the Harish-Chandra-Itzykson-Zuber integral, which comes from the theory of random matrices and has applications in mathematical physics. The connection between random matrices and permutation factorizations goes through representation theory, with symmetric functions in the Jucys-Murphy elements playing a key role. As the name implies, monotone Hurwitz numbers are related to the more classical Hurwitz numbers, which count permutation factorizations regardless of monotonicity, and for which there is a significant body of work. Our results for monotone Hurwitz numbers are inspired by similar results for Hurwitz numbers; we obtain a genus expansion for the related generating functions, which yields explicit formulas and a polynomiality result for monotone Hurwitz numbers. A significant difference between the two cases is that our methods are purely algebraic, whereas the theory of Hurwitz numbers relies on some fairly deep results in algebraic geometry. Despite our methods being algebraic, it seems that there should be a connection between monotone Hurwitz numbers and geometry, although this is currently missing. We give some evidence for this connection by identifying some of the coefficients in the monotone Hurwitz genus expansion with coefficients in the classical Hurwitz genus expansion known to be Hodge integrals over the moduli space of curves.
Algebraic Methods for Reducibility in Nowhere-Zero Flows
(University of Waterloo, 2007-09-25T20:53:28Z) Li, Zhentao
We study reducibility for nowhere-zero flows. A reducibility proof typically consists of showing that some induced subgraphs cannot appear in a minimum counter-example to some conjecture. We derive algebraic proofs of reducibility. We define variables which in some sense count the number of nowhere-zero flows of certain type in a graph and then deduce equalities and inequalities that must hold for all graphs. We then show how to use these algebraic expressions to prove reducibility. In our case, these inequalities and equalities are linear. We can thus use the well developed theory of linear programming to obtain certificates of these proof. We make publicly available computer programs we wrote to generate the algebraic expressions and obtain the certificates.
Algebraic Tori in Cryptography
(University of Waterloo, 2005) Alexander, Nicholas Charles
Communicating bits over a network is expensive. Therefore, cryptosystems that transmit as little data as possible are valuable. This thesis studies several cryptosystems that require significantly less bandwidth than conventional analogues. The systems we study, called torus-based cryptosystems, were analyzed by Karl Rubin and Alice Silverberg in 2003 [RS03]. They interpreted the XTR [LV00] and LUC [SL93] cryptosystems in terms of quotients of algebraic tori and birational parameterizations, and they also presented CEILIDH, a new torus-based cryptosystem. This thesis introduces the geometry of algebraic tori, uses it to explain the XTR, LUC, and CEILIDH cryptosystems, and presents torus-based extensions of van Dijk, Woodruff, et al. [vDW04, vDGP⁺05] that require even less bandwidth. In addition, a new algorithm of Granger and Vercauteren [GV05] that attacks the security of torus-based cryptosystems is presented. Finally, we list some open research problems.
Algorithm Design for Ordinal Settings
(University of Waterloo, 2022-08-29) Pulyassary, Haripriya
Social choice theory is concerned with aggregating the preferences of agents into a single outcome. While it is natural to assume that agents have cardinal utilities, in many contexts, we can only assume access to the agents’ ordinal preferences, or rankings over the outcomes. As ordinal preferences are not as expressive as cardinal utilities, a loss of efficiency is unavoidable. Procaccia and Rosenschein (2006) introduced the notion of distortion to quantify this worst-case efficiency loss for a given social choice function. We primarily study distortion in the context of election, or equivalently clustering problems, where we are given a set of agents and candidates in a metric space; each agent has a preference ranking over the set of candidates and we wish to elect a committee of k candidates that minimizes the total social cost incurred by the agents. In the single-winner setting (when k = 1), we give a novel LP-duality based analysis framework that makes it easier to analyze the distortion of existing social choice functions, and extends readily to randomized social choice functions. Using this framework, we show that it is possible to give simpler proofs of known results. We also show how to efficiently compute an optimal randomized social choice function for any given instance. We utilize the latter result to obtain an instance for which any randomized social choice function has distortion at least 2.063164. This disproves the long-standing conjecture that there exists a randomized social choice function that has a worst-case distortion of at most 2. When k is at least 2, it is not possible to compute an O(1)-distortion committee using purely ordinal information. We develop two O(1)-distortion mechanisms for this problem: one having a polylog(n) (per agent) query complexity, where n is the number of agents; and the other having O(k) query complexity (i.e., no dependence on n). We also study a much more general setting called minimum-norm k-clustering recently proposed in the clustering literature, where the objective is some monotone, symmetric norm of the the agents' costs, and we wish to find a committee of k candidates to minimize this objective. When the norm is the sum of the p largest costs, which is called the p-centrum problem in the clustering literature, we give low-distortion mechanisms by adapting our mechanisms for k-median. En route, we give a simple adaptive-sampling algorithm for this problem. Finally, we show how to leverage this adaptive-sampling idea to also obtain a constant-factor bicriteria approximation algorithm for minimum-norm k-clustering (in its full generality).
An Algorithm for Stable Matching with Approximation up to the Integrality Gap
(University of Waterloo, 2020-07-10) Tofigzade, Natig
In the stable matching problem we are given a bipartite graph G = (A ∪ B, E) where A and B represent disjoint groups of agents, each of whom has ordinal preferences over the members of the opposite group. The goal is to find an assignment of agents in one group to those in the other such that no pair of agents prefer each other to their assignees. In this thesis we study the stable matching problem with ties and incomplete preferences. If agents are allowed to have ties and incomplete preferences, computing a stable matching of maximum cardinality is known to be NP-hard. Furthermore, it is known to be NP-hard to achieve a performance guarantee of 33/29 − ε (≈ 1.1379) and UGC-hard to attain that of 4/3 − ε (≈ 1.3333). We present a polynomial-time approximation algorithm with a performance guarantee of (3L − 2)/(2L − 1) where L is the maximum tie length. Our result matches the known lower bound on the integrality gap for the associated LP formulation.
Algorithm Substitution Attacks: Detecting ASAs Using State Reset and Making ASAs Asymmetric
(University of Waterloo, 2021-08-27) Hodges, Philip
The field of cryptography has made incredible progress in the last several decades. With the formalization of security goals and the methods of provable security, we have achieved many privacy and integrity guarantees in a great variety of situations. However, all guarantees are limited by their assumptions on the model's adversaries. Edward Snowden's revelations of the participation of the National Security Agency (NSA) in the subversion of standardized cryptography have shown that powerful adversaries will not always act in the way that common cryptographic models assume. As such, it is important to continue to expand the capabilities of the adversaries in our models to match the capabilities and intentions of real world adversaries, and to examine the consequences on the security of our cryptography. In this thesis, we study Algorithm Substitution Attacks (ASAs), which are one way to model this increase in adversary capability. In an ASA, an algorithm in a cryptographic scheme Λ is substituted for a subverted version. The goal of the adversary is to recover a secret that will allow them to compromise the security of Λ, while requiring that the attack is undetectable to the users of the scheme. This model was first formally described by Bellare, Paterson, and Rogaway (Crypto 2014), and allows for the possibility of a wide variety of cryptographic subversion techniques. Since their paper, many successful ASAs on various cryptographic primitives and potential countermeasures have been demonstrated. We will address several shortcomings in the existing literature. First, we formalize and study the use of state resets to detect ASAs. While state resets have been considered as a possible detection method since the first papers on ASAs, future works have only informally reasoned about the effect of state resets on ASAs. We show that many published ASAs that use state are detectable with simple practical methods relying on state resets. Second, we add to the study of asymmetric ASAs, where the ability to recover secrets is restricted to the attacker who implemented the ASA. We describe two asymmetric ASAs on symmetric encryption based on modifications to previous ASAs. We also generalize this result, allowing for any symmetric ASA (on any cryptographic scheme) satisfying certain properties to be transformed into an asymmetric ASA. This work demonstrates the broad application of the techniques first introduced by Bellare, Paterson, and Rogaway (Crypto 2014) and Bellare, Jaeger, and Kane (CCS 2015) and reinforces the need for precise definitions surrounding detectability of stateful ASAs.
Algorithmic and Linear Programming-Based Techniques for the Maximum Utility Problem
(University of Waterloo, 2023-05-25) Lawrence, Paul
A common topic of study in the subfield of Operations Research known as Revenue Management is finding optimal prices for a line of products given customer preferences. While there exists a large number of ways to model optimal pricing problems, in this thesis we study a price-based Revenue Management model known as the Maximum Utility Problem (MUP). In this model, we are given a set of n customer segments and m products, as well as reservation prices Rij which reflect the amount that Segment i is willing to pay for Product j. Using a number of structural and behavioral assumptions, if we derive a vector of prices for our line of products, we can compute an assignment of customers to products. We wish to find the set of prices that leads to the optimal amount of revenue given our rules for assigning customers to products. Using this framework, we can formulate a Nonlinear Mixed Integer Programming formulation that, while difficult to solve, has a surprising amount of underlying structure. If we fix an assignment and simply ask for the optimal set of prices such that said assignment is feasible, we obtain a new linear program, the dual of which happens to be a set of shortest-paths problems. This fact lead to the development of the Dobson-Kalish Algorithm, which explores a large number of assignments and quickly computes their optimal prices. Since the introduction of the Dobson-Kalish Algorithm, there has been a rich variety of literature surrounding MUP and its relatives. These include the introduction of utility tolerances to increase the robustness of the model, as well as new approximation algorithms, hardness results, and insights into the underlying combinatorial structure of the problem. After detailing this history, this thesis discusses a range of settings under which MUP can be solved in polynomial time. Relating it to other equilibria and price-based optimization problems, we overview Stackelberg Network Pricing Games as well as the general formulations of Bilevel Mixed Integer Linear Programs and Bilinear Mixed Integer Programs, showing that our formulation of the latter is in fact a more general version of the former. We provide some new structured instances for which we can prove additional ap- proximation and runtime results for existing algorithms. We also contribute a generalized heuristic algorithm and show that MUP can be solved exactly when the matrix of reservation prices is rank 1. Finally, we discuss techniques for improving the upper bound to the overall problem, analyzing the primal and dual of the linear programming relaxation of MUP. To test the effectiveness of our approach, we analyze numerous examples that have been solved using Gurobi and present possible avenues for improving our ideas.
Algorithms for Analytic Combinatorics in Several Variables
(University of Waterloo, 2023-04-25) Smolcic, Josip
Given a multivariate rational generating function we are interested in computing asymptotic formulas for the sequences encoded by the coefficients. In this thesis we apply the theory of analytic combinatorics in several variables (ACSV) to this problem and build algorithms which seek to compute asymptotic formulas automatically, and to aid in understanding of the theory. Under certain assumptions on a given rational multivariate generating series, we demonstrate two algorithms which compute an asymptotic formula for the coefficients. The first algorithm applies numerical methods for polynomial system solving to compute minimal points which are essential to asymptotics, while the second algorithm leverages the geometry of a so-called height map in two variables to compute asymptotics even in the absence of minimal points. We also provide software for computing gradient flows on the height maps of rational generating functions. These flows are useful for understanding the deformations of integral contours which are present in the analysis of rational generating functions.
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}.
Analyzing Quantum Cryptographic Protocols Using Optimization Techniques
(University of Waterloo, 2012-05-22T17:53:41Z) Sikora, Jamie William Jonathon
This thesis concerns the analysis of the unconditional security of quantum cryptographic protocols using convex optimization techniques. It is divided into the study of coin-flipping and oblivious transfer. We first examine a family of coin-flipping protocols. Almost all of the handful of explicitly described coin-flipping protocols are based on bit-commitment. To explore the possibility of finding explicit optimal or near-optimal protocols, we focus on a class which generalizes such protocols. We call these $\BCCF$-protocols, for bit-commitment based coin-flipping. We use the semidefinite programming (SDP) formulation of cheating strategies along the lines of Kitaev to analyze the structure of the protocols. In the first part of the thesis, we show how these semidefinite programs can be used to simplify the analysis of the protocol. In particular, we show that a particular set of cheating strategies contains an optimal strategy. This reduces the problem to optimizing a linear combination of fidelity functions over a polytope which has several benefits. First, it allows one to model cheating probabilities using a simpler class of optimization problems known as second-order cone programs (SOCPs). Second, it helps with the construction of point games due to Kitaev as described in Mochon's work. Point games were developed to give a new perspective for studying quantum protocols. In some sense, the notion of point games is dual to the notion of protocols. There has been increased research activity in optimization concerning generalizing theory and algorithms for linear programming to much wider classes of optimization problems such as semidefinite programming. For example, semidefinite programming provides a tool for potentially improving results based on linear programming or investigating old problems that have eluded analysis by linear programming. In this sense, the history of semidefinite programming is very similar to the history of quantum computation. Quantum computing gives a generalized model of computation to tackle new and old problems, improving on and generalizing older classical techniques. Indeed, there are striking differences between linear programming and semidefinite programming as there are between classical and quantum computation. In this thesis, we strengthen this analogy by studying a family of classical coin-flipping protocols based on classical bit-commitment. Cheating strategies for these ``classical $\BCCF$-protocols'' can be formulated as linear programs (LPs) which are closely related to the semidefinite programs for the quantum version. In fact, we can construct point games for the classical protocols as well using the analysis for the quantum case. Using point games, we prove that every classical $\BCCF$-protocol allows exactly one of the parties to entirely determine the outcome. Also, we rederive Kitaev's lower bound to show that only ``classical'' protocols can saturate Kitaev's analysis. Moreover, if the product of Alice and Bob's optimal cheating probabilities is $1/2$, then at least one party can cheat with probability $1$. The second part concerns the design of an algorithm to search for $\BCCF$-protocols with small bias. Most coin-flipping protocols with more than three rounds have eluded direct analysis. To better understand the properties of optimal $\BCCF$-protocols with four or more rounds, we turn to computational experiments. We design a computational optimization approach to search for the best protocol based on the semidefinite programming formulations of cheating strategies. We create a protocol filter using cheating strategies, some of which build upon known strategies and others are based on convex optimization and linear algebra. The protocol filter efficiently eliminates candidate protocols with too high a bias. Using this protocol filter and symmetry arguments, we perform searches in a matter of days that would have otherwise taken millions of years. Our experiments checked $10^{16}$ four and six-round $\BCCF$-protocols and suggest that the optimal bias is $1/4$. The third part examines the relationship between oblivious transfer, bit-commitment, and coin-flipping. We consider oblivious transfer which succeeds with probability $1$ when the two parties are honest and construct a simple protocol with security provably better than any classical protocol. We also derive a lower bound by constructing a bit-commitment protocol from an oblivious transfer protocol. Known lower bounds for bit-commitment then lead to a constant lower bound on the bias of oblivious transfer. Finally, we show that it is possible to use Kitaev's semidefinite programming formulation of cheating strategies to obtain optimal lower bounds on a ``forcing'' variant of oblivious transfer related to coin-flipping.
Analyzing Tree Attachments in 2-Crossing-Critical Graphs with a V8 Minor
(University of Waterloo, 2023-04-25) Bedsole, Carter
The crossing number of a graph is the minimum number of pairwise edge crossings in a drawing of the graph in the plane. A graph G is k-crossing-critical if its crossing number is at least k and if every proper subgraph H of G has crossing number less than k. It follows directly from Kuratowski's Theorem that the 1-crossing-critical graphs are precisely the subdivisions of K{3,3} and K5. Characterizing the 2-crossing-critical graphs is an interesting open problem. Much progress has been made in characterizing the 2-crossing-critical graphs. The only remaining unexplained such graphs are those which are 3-connected, have a V8 minor but no V10 minor, and embed in the real projective plane. This thesis seeks to extend previous attempts at classifying this particular set of graphs by examining the graphs in this category where a tree structure is attached to a subdivision of V8. In this paper, we analyze which of the 106 possible 3-stars can be attached to a subdivision H of V8 in a 3-connected 2-crossing-critical graph. This analysis leads to a strong result, where we demonstrate that if a k-star is attached to a V8 in a 2-crossing-critical graph, then k <= 4. Finally, we significantly restrict the remaining trees which still need to be investigated under the same conditions.

Browse

Browsing Combinatorics and Optimization by Title