In this thesis, we investigate the cost of finding collisions in a black-box function, a problem that is of fundamental importance in cryptanalysis. Inspired by the excellent performance of the heuristic rho method of collision finding, we define several new models of complexity that take into account the cost of moving information across a large space, and lay the groundwork for studying the performance of classical and quantum algorithms in these models.

The Trust Region Subproblem (TRS) is the problem of minimizing a quadratic (possibly non-convex) function over a sphere. It is the main step of the trust region method for unconstrained optimization problems. Two cases may cause numerical difficulties in solving the TRS, i.e., (i) the so-called hard case and (ii) having a large trust region radius. In this thesis we give the optimality characteristics of the TRS and review the major current algorithms. Then we introduce some techniques to solve the TRS efficiently for the two difficult cases. A shift and deflation technique avoids the hard case; and a scaling can adjust the value of the trust region radius. In addition, we illustrate other improvements for the TRS algorithm, including: rotation, approximate eigenvalue calculations, and inverse polynomial interpolation. We also introduce a warm start approach and include a new treatment for the hard case for the trust region method. Sensitivity analysis is provided to show that the optimal objective value for the TRS is stable with respect to the trust region radius in both the easy and hard cases. Finally, numerical experiments are provided to show the performance of all the improvements.

In this thesis, we investigate the cost of finding collisions in a black-box function, a problem that is of fundamental importance in cryptanalysis. Inspired by the excellent performance of the heuristic rho method of collision finding, we define several new models of complexity that take into account the cost of moving information across a large space, and lay the groundwork for studying the performance of classical and quantum algorithms in these models.

The Trust Region Subproblem (TRS) is the problem of minimizing a quadratic (possibly non-convex) function over a sphere. It is the main step of the trust region method for unconstrained optimization problems. Two cases may cause numerical difficulties in solving the TRS, i.e., (i) the so-called hard case and (ii) having a large trust region radius. In this thesis we give the optimality characteristics of the TRS and review the major current algorithms. Then we introduce some techniques to solve the TRS efficiently for the two difficult cases. A shift and deflation technique avoids the hard case; and a scaling can adjust the value of the trust region radius. In addition, we illustrate other improvements for the TRS algorithm, including: rotation, approximate eigenvalue calculations, and inverse polynomial interpolation. We also introduce a warm start approach and include a new treatment for the hard case for the trust region method. Sensitivity analysis is provided to show that the optimal objective value for the TRS is stable with respect to the trust region radius in both the easy and hard cases. Finally, numerical experiments are provided to show the performance of all the improvements.

The problem of pricing a product line to maximize profits is an important challenge faced by many companies. To address this problem, we discuss four different probabilistic choice models that are based on reservation prices: the Uniform Distribution Model, the Weighted Uniform Model, the Share-of-Surplus Model, and the Price Sensitive Model. They are formulated as convex mixed-integer mathematical programs. We explore the properties and additional valid inequalities of these formulations. We also compare their optimal solutions on a set of inputs. In general, the Uniform Distribution, Weighted Uniform, and Price Sensitive Models have the same optimal solution while the Share-of-Surplus Model gives a different solution in many cases. We develop a few heuristics for finding good feasible solutions. These simple and efficient heuristics perform well and help to improve the solution time. Computational results of solving problem instances of various sizes are shown.

The problem of pricing a product line to maximize profits is an important challenge faced by many companies. To address this problem, we discuss four different probabilistic choice models that are based on reservation prices: the Uniform Distribution Model, the Weighted Uniform Model, the Share-of-Surplus Model, and the Price Sensitive Model. They are formulated as convex mixed-integer mathematical programs. We explore the properties and additional valid inequalities of these formulations. We also compare their optimal solutions on a set of inputs. In general, the Uniform Distribution, Weighted Uniform, and Price Sensitive Models have the same optimal solution while the Share-of-Surplus Model gives a different solution in many cases. We develop a few heuristics for finding good feasible solutions. These simple and efficient heuristics perform well and help to improve the solution time. Computational results of solving problem instances of various sizes are shown.

Informally, a rooted map is a topologically pointed embedding of a graph in a surface. This thesis examines two problems in the enumerative theory of rooted maps. The b-Conjecture, due to Goulden and Jackson, predicts that structural similarities between the generating series for rooted orientable maps with respect to vertex-degree sequence, face-degree sequence, and number of edges, and the corresponding generating series for rooted locally orientable maps, can be explained by a unified enumerative theory. Both series specialize M(x,y,z;b), a series defined algebraically in terms of Jack symmetric functions, and the unified theory should be based on the existence of an appropriate integer valued invariant of rooted maps with respect to which M(x,y,z;b) is the generating series for locally orientable maps. The conjectured invariant should take the value zero when evaluated on orientable maps, and should take positive values when evaluated on non-orientable maps, but since it must also depend on rooting, it cannot be directly related to genus. A new family of candidate invariants, η, is described recursively in terms of root-edge deletion. Both the generating series for rooted maps with respect to η and an appropriate specialization of M satisfy the same differential equation with a unique solution. This shows that η gives the appropriate enumerative theory when vertex degrees are ignored, which is precisely the setting required by Goulden, Harer, and Jackson for an application to algebraic geometry. A functional equation satisfied by M and the existence of a bijection between rooted maps on the torus and a restricted set of rooted maps on the Klein bottle show that η has additional structural properties that are required of the conjectured invariant. The q-Conjecture, due to Jackson and Visentin, posits a natural combinatorial explanation, for a functional relationship between a generating series for rooted orientable maps and the corresponding generating series for 4-regular rooted orientable maps. The explanation should take the form of a bijection, ϕ, between appropriately decorated rooted orientable maps and 4-regular rooted orientable maps, and its restriction to undecorated maps is expected to be related to the medial construction. Previous attempts to identify ϕ have suffered from the fact that the existing derivations of the functional relationship involve inherently non-combinatorial steps, but the techniques used to analyze η suggest the possibility of a new derivation of the relationship that may be more suitable to combinatorial analysis. An examination of automorphisms that must be induced by ϕ gives evidence for a refinement of the functional relationship, and this leads to a more combinatorially refined conjecture. The refined conjecture is then reformulated algebraically so that its predictions can be tested numerically.

This thesis concerns sufficient conditions for a matroid to admit one of two types of structural characterization: a representation over a finite field or a description as a frame matroid. We call a restriction N of a matroid M modular if, for every flat F of M, r_M(F) + r(N) = r_M(F ∩ E(N)) + r_M(F ∪ E(N)). A consequence of a theorem of Seymour is that any 3-connected matroid with a modular U_{2,3}-restriction is binary. We extend this fact to arbitrary finite fields, showing that if N is a modular rank-3 restriction of a vertically 4-connected matroid M, then any representation of N over a finite field extends to a representation of M. We also look at a more general notion of modularity that applies to minors of a matroid, and use it to present conditions for a matroid with a large projective geometry minor to be representable over a finite field. In particular, we show that a 3-connected, representable matroid with a sufficiently large projective geometry over a finite field GF(q) as a minor is either representable over GF(q) or has a U_{2,q^2+1}-minor. A second result of Seymour is that any vertically 4-connected matroid with a modular M(K_4)-restriction is graphic. Geelen, Gerards, and Whittle partially generalized this from M(K_4) to larger frame matroids, showing that any vertically 5-connected, representable matroid with a rank-4 Dowling geometry as a modular restriction is a frame matroid. As with projective geometries, we prove a version of this result for matroids with large Dowling geometries as minors, providing conditions which imply that they are frame matroids.

Coin-flipping is the cryptographic task of generating a random coin-flip between two mistrustful parties. Kitaev discovered that the security of quantum coin-flipping protocols can be analyzed using semidefinite programming. This lead to his result that one party can force a desired coin-flip outcome with probability at least 1/√2. We give sufficient background in quantum computing and semidefinite programming to understand Kitaev's semidefinite programming formulation for coin-flipping cheating strategies. These ideas are specialized to a specific class of protocols singled out by Nayak and Shor. We also use semidefinite programming to solve for the maximum cheating probability of a particular protocol which has the best known security. Furthermore, we present a family of protocols where one party has a greater probability of forcing an outcome of 0 than an outcome of 1. We also discuss a computer search to find specific protocols which minimize the maximum cheating probability.

Informally, a rooted map is a topologically pointed embedding of a graph in a surface. This thesis examines two problems in the enumerative theory of rooted maps. The b-Conjecture, due to Goulden and Jackson, predicts that structural similarities between the generating series for rooted orientable maps with respect to vertex-degree sequence, face-degree sequence, and number of edges, and the corresponding generating series for rooted locally orientable maps, can be explained by a unified enumerative theory. Both series specialize M(x,y,z;b), a series defined algebraically in terms of Jack symmetric functions, and the unified theory should be based on the existence of an appropriate integer valued invariant of rooted maps with respect to which M(x,y,z;b) is the generating series for locally orientable maps. The conjectured invariant should take the value zero when evaluated on orientable maps, and should take positive values when evaluated on non-orientable maps, but since it must also depend on rooting, it cannot be directly related to genus. A new family of candidate invariants, η, is described recursively in terms of root-edge deletion. Both the generating series for rooted maps with respect to η and an appropriate specialization of M satisfy the same differential equation with a unique solution. This shows that η gives the appropriate enumerative theory when vertex degrees are ignored, which is precisely the setting required by Goulden, Harer, and Jackson for an application to algebraic geometry. A functional equation satisfied by M and the existence of a bijection between rooted maps on the torus and a restricted set of rooted maps on the Klein bottle show that η has additional structural properties that are required of the conjectured invariant. The q-Conjecture, due to Jackson and Visentin, posits a natural combinatorial explanation, for a functional relationship between a generating series for rooted orientable maps and the corresponding generating series for 4-regular rooted orientable maps. The explanation should take the form of a bijection, ϕ, between appropriately decorated rooted orientable maps and 4-regular rooted orientable maps, and its restriction to undecorated maps is expected to be related to the medial construction. Previous attempts to identify ϕ have suffered from the fact that the existing derivations of the functional relationship involve inherently non-combinatorial steps, but the techniques used to analyze η suggest the possibility of a new derivation of the relationship that may be more suitable to combinatorial analysis. An examination of automorphisms that must be induced by ϕ gives evidence for a refinement of the functional relationship, and this leads to a more combinatorially refined conjecture. The refined conjecture is then reformulated algebraically so that its predictions can be tested numerically.