It is known that almost all 2-qubit gates are universal for quantum computing (Lloyd 1995; Deutsch, Barenco, Eckert 1995). However, an explicit characterization of non-universal 2-qubit gates is not known. We consider a closely related problem of characterizing the set of non-universal 2-qubit Hamiltonians. We call a 2-qubit Hamiltonian n-universal if, when applied on different pairs of qubits, it can be used to approximate any unitary operation on n qubits. It follows directly from the results of Lloyd and Deutsch, Barenco, Eckert, that almost any 2-qubit Hamiltonian is 2-universal. Our main result is a complete characterization of 2-non-universal 2-qubit Hamiltonians. There are three cases when a 2-qubit Hamiltonian H is not universal: (1) H shares an eigenvector with the gate that swaps two qubits; (2) H acts on the two qubits independently (in any of a certain family of bases); (3) H has zero trace. The last condition rules out the Hamiltonians that generate SU(4)---it can be omitted if the global phase is not important. A Hamiltonian that is not 2-universal can still be 3-universal. We give a (possibly incomplete) list of 2-qubit Hamiltonians that are not 3-universal. If this list happens to be complete, it actually gives a classification of n-universal 2-qubit Hamiltonians for all n >= 3.

Zip.ca is an online DVD rental company that faces two major operational problems: calculation of the assignment of DVDs to customers every thirty minutes throughout the day and purchasing of new inventory in regular intervals. In this thesis, we model these two problems and develop algorithms to solve them. In doing so, we encounter many theoretical problems that are both applicable to Zip’s operations and intrinsically interesting problems independent of the application. First, we note that the assignment problem facing Zip is inherently in an online setting. With returns of DVDs being processed throughout the day, the dataset is constantly changing. Although the ideal solution would be to wait until the end of the day to make decisions, physical work load capacities prevent this. For this reason we discuss two online problems, online 0-1 budgeted matching and the budgeted Adwords auction. We present a 1/(2 w_max/w_min)-competitive algorithm for the online 0-1 budgeted matching problem, and prove that this is the best possible competitive ratio possible for a wide class of algorithms. We also give a (1− (S+1)/(S+e) )-competitive algorithm for the budgeted Adwords auction as the size of the bids and cost get small compared to the budgets, where S is the ratio of the highest and lowest ratios of bids to costs. We suggest a linear programming approach to solve Zip’s assignment problem. We develop an integer program that models the B-matching instance with additional constraints of concern to Zip, and prove that this integer program belongs to a larger class of integer programs that has totally unimodular constraint matrices. Thus, the assignment problem can be solved to optimality every thirty minutes. We additionally create a test environment to check daily performance, and provide real-time implementation results, showing a marked improvement over Zip’s old algorithm. We show that Zip’s purchasing problem can be modeled by the matching augmentation problem defined as follows. Given a graph with vertex capacities and costs, edge weights, and budget C, find a purchasing of additional node capacity of cost at most C that admits a B-matching of maximum weight. We give a PTAS for this problem, and then present a special case that is polynomial time solvable that still models Zip’s purchasing problem, under the assumption of uniform costs. We then extend the augmentation idea to matroids and present matroid augmentation, matroid knapsack, and matroid intersection knapsack, three NP-hard problems. We give an FPTAS for matroid knapsack by dynamic programming, PTASes for the other two, and demonstrate applications of these problems.

The study of the infinite (countable) family of partial differential equations known as the Kadomtzev - Petviashvili (KP) hierarchy has received much interest in the mathematical and theoretical physics community for over forty years. Recently there has been a renewed interest in its application to enumerative combinatorics inspired by Witten's conjecture (now Kontsevich's theorem). In this thesis we provide a detailed development of the KP hierarchy and some of its applications with an emphasis on the combinatorics involved. Up until now, most of the material pertaining to the KP hierarchy has been fragmented throughout the physics literature and any complete accounts have been for purposes much diff erent than ours. We begin by describing a family of related Lie algebras along with a module on which they act. We then construct a realization of this module in terms of polynomials and determine the corresponding Lie algebra actions. By doing this we are able to describe one of the Lie group orbits as a family of polynomials and the equations that de fine them as a family of partial diff erential equations. This then becomes the KP hierarchy and its solutions. We then interpret the KP hierarchy as a pair of operators on the ring of symmetric functions and describe their action combinatorially. We then conclude the thesis with some combinatorial applications.

We study a new method of generating random $d$-regular graphs by repeatedly applying an operation called pegging. The pegging algorithm, which applies the pegging operation in each step, is a method of generating large random regular graphs beginning with small ones. We prove that the limiting joint distribution of the numbers of short cycles in the resulting graph is independent Poisson. We use the coupling method to bound the total variation distance between the joint distribution of short cycle counts and its limit and thereby show that $O(\epsilon^{-1})$ is an upper bound of the $\eps$-mixing time. The coupling involves two different, though quite similar, Markov chains that are not time-homogeneous. We also show that the $\epsilon$-mixing time is not $o(\epsilon^{-1})$. This demonstrates that the upper bound is essentially tight. We study also the connectivity of random $d$-regular graphs generated by the pegging algorithm. We show that these graphs are asymptotically almost surely $d$-connected for any even constant $d\ge 4$. The problem of orientation of random hypergraphs is motivated by the classical load balancing problem. Let $h>w>0$ be two fixed integers. Let $\orH$ be a hypergraph whose hyperedges are uniformly of size $h$. To {\em $w$-orient} a hyperedge, we assign exactly $w$ of its vertices positive signs with respect to this hyperedge, and the rest negative. A $(w,k)$-orientation of $\orH$ consists of a $w$-orientation of all hyperedges of $\orH$, such that each vertex receives at most $k$ positive signs from its incident hyperedges. When $k$ is large enough, we determine the threshold of the existence of a $(w,k)$-orientation of a random hypergraph. The $(w,k)$-orientation of hypergraphs is strongly related to a general version of the off-line load balancing problem. The other topic we discuss is computing the probability of induced subgraphs in a random regular graph. Let $0<s<n$ and $H$ be a graph on $s$ vertices. For any $S\subset [n]$ with $|S|=s$, we compute the probability that the subgraph of $\mathcal{G}_{n,d}$ induced by $S$ is $H$. The result holds for any $d=o(n^{1/3})$ and is further extended to $\mathcal{G}_{n,{\bf d}}$, the probability space of random graphs with given degree sequence $\bf d$. This result provides a basic tool for studying properties, for instance the existence or the counts, of certain types of induced subgraphs.

The Time-Dependent Traveling Salesman Problem is a generalization of the well-known Traveling Salesman Problem, where the cost for travel between two nodes is dependent on the nodes and their position in the tour. Inequalities for the Asymmetric TSP can be easily extended to the TDTSP, but the added time information can be used to strengthen these inequalities. We look at extending the Lifted Cycle Inequalities, a large family of inequalities for the ATSP. We define a new inequality, the Extended Cycle (X-cycle) Inequality, based on cycles in the graph. We extend the results of Balas and Fischetti for Lifted Cycle Inequalities to define Lifted X-cycle Inequalities. We show that the Lifted X-cycle Inequalities include some inequalities which define facets of the submissive of the TDTS Polytope.

An isogeny between elliptic curves is an algebraic morphism which is a group homomorphism. Many applications in cryptography require evaluating large degree isogenies between elliptic curves efficiently. For ordinary curves of the same endomorphism ring, the previous fastest algorithm known has a worst case running time which is exponential in the length of the input. In this thesis we solve this problem in subexponential time under reasonable heuristics. We give two versions of our algorithm, a slower version assuming GRH and a faster version assuming stronger heuristics. Our approach is based on factoring the ideal corresponding to the kernel of the isogeny, modulo principal ideals, into a product of smaller prime ideals for which the isogenies can be computed directly. Combined with previous work of Bostan et al., our algorithm yields equations for large degree isogenies in quasi-optimal time given only the starting curve and the kernel.

The central theme of this thesis is to prove results about infinite mathematical objects by studying the behaviour of their finite substructures. In particular, we study B-matroids, which are an infinite generalization of matroids introduced by Higgs \cite{higgs}, and graph-like spaces, which are topological spaces resembling graphs, introduced by Thomassen and Vella \cite{thomassenvella}. Recall that the circuit matroid of a finite graph is a matroid defined on the edges of the graph, with a set of edges being independent if it contains no circuit. It turns out that graph-like continua and infinite graphs both have circuit B-matroids. The first main result of this thesis is a generalization of Whitney's Theorem that a graph has an abstract dual if and only if it is planar. We show that an infinite graph has an abstract dual (which is a graph-like continuum) if and only if it is planar, and also that a graph-like continuum has an abstract dual (which is an infinite graph) if and only if it is planar. This generalizes theorems of Thomassen (\cite{thomassendual}) and Bruhn and Diestel (\cite{bruhndiestel}). The difficult part of the proof is extending Tutte's characterization of graphic matroids (\cite{tutte2}) to finitary or co-finitary B-matroids. In order to prove this characterization, we introduce a technique for obtaining these B-matroids as the limit of a sequence of finite minors. In \cite{tutte}, Tutte proved important theorems about the peripheral (induced and non-separating) circuits of a $3$-connected graph. He showed that for any two edges of a $3$-connected graph there is a peripheral circuit containing one but not the other, and that the peripheral circuits of a $3$-connected graph generate its cycle space. These theorems were generalized to $3$-connected binary matroids by Bixby and Cunningham (\cite{bixbycunningham}). We generalize both of these theorems to $3$-connected binary co-finitary B-matroids. Richter, Rooney and Thomassen \cite{richterrooneythomassen} showed that a locally connected, compact metric space has an embedding in the sphere unless it contains a subspace homeomorphic to $K_5$ or $K_{3,3}$, or one of a small number of other obstructions. We are able to extend this result to an arbitrary surface $\Sigma$; a locally connected, compact metric space embeds in $\Sigma$ unless it contains a subspace homeomorphic to a finite graph which does not embed in $\Sigma$, or one of a small number of other obstructions.

In this thesis we consider two classes of binary matroids, even cycle matroids and even cut matroids. They are a generalization of graphic and cographic matroids respectively. We focus on two main problems for these classes of matroids. We first consider the Isomorphism Problem, that is the relation between two representations of the same matroid. A representation of an even cycle matroid is a pair formed by a graph together with a special set of edges of the graph. Such a pair is called a signed graph. A representation for an even cut matroid is a pair formed by a graph together with a special set of vertices of the graph. Such a pair is called a graft. We show that two signed graphs representing the same even cycle matroid relate to two grafts representing the same even cut matroid. We then present two classes of signed graphs and we solve the Isomorphism Problem for these two classes. We conjecture that any two representations of the same even cycle matroid are either in one of these two classes, or are related by a local modification of a known operation, or form a sporadic example. The second problem we consider is finding the excluded minors for these classes of matroids. A difficulty when looking for excluded minors for these classes arises from the fact that in general the matroids may have an arbitrarily large number of representations. We define degenerate even cycle and even cut matroids. We show that a 3-connected even cycle matroid containing a 3-connected non-degenerate minor has, up to a simple equivalence relation, at most twice as many representations as the minor. We strengthen this result for a particular class of non-degenerate even cycle matroids. We also prove analogous results for even cut matroids.

For any finite set B and a subset A⊆B, we define the density of A in B to be the value α=|A|/|B|. Roth's famous theorem, proven in 1953, states that there is a constant C>0, such that if A⊆{1,...,N} for a positive integer N and A has density α in {1,...,N} with α>C/loglog N, then A contains a non-trivial arithmetic progression of length three (3AP). The proof of this relies on the following dichotomy: either 1) A looks like a random set and the number of 3APs in A is close to the probabilistic expected value, or 2) A is more structured and consequently, there is a progression P of about length α√N on which A∩P has α(1+cα) for some c>0. If 1) occurs, then we are done. If 2) occurs, then we identify P with {1,...,|P|} and repeat the above argument, whereby the density increases at each iteration of the dichotomy. Due to the density increase in case 2), an argument of this type is called a density increment argument. The density increment is obtained by studying the Fourier transforms of the characterstic function of A and extracting a structure out of A. Improving the lower bound for α is still an active area of research and all improvements so far employ a density increment. Two of the most recent results are α>C(loglog N/log N)^{1/2} by Bourgain in 1999 and α>C(loglog N)^5/log N by Sanders in 2010. This thesis is a survey of progresses in Roth's theorem, with a focus on these last two results. Attention was given to unifying the language in which the results are discussed and simplifying the presentation.

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.