As soon as Bennett and Gill first demonstrated that, relative to a randomly chosen oracle, P is not equal to NP with probability 1, the random oracle hypothesis began piquing the interest of mathematicians and computer scientists. This was quickly disproven in several ways, most famously in 1992 with the result that IP equals PSPACE, in spite of the classes being shown unequal with probability 1. Here, we propose what could be considered strengthening of the random oracle hypothesis, using a stricter notion of what it means for a set to be 'large'. In particular, we suggest using largeness with respect to the Ramsey forcing notion. In this new context, we demonstrate that the set of oracles separating NP and coNP is 'not small', and obtain similar results for the separation of PSPACE from PH along with the separation of NP from BQP. In a related set of results, we demonstrate that these classes are all of the same descriptive complexity. Finally we demonstrate that this strengthening of the hypothesis turns it into a sufficient condition for unrelativized relationships, at least in the three cases considered here.

This dissertation is in the area of complex dynamics, more specifically focused on the iteration of rational functions. Given a well-chosen family of rational functions, parameterized by a complex parameter, we are especially interested in regularity properties of the Hausdorff dimension of Julia sets of these polynomials considered as a function of the parameters. In this dissertation I deal with a family of polynomials of degree at least 3 depending in a holomorphic way on a parameter, focusing on the point where the dynamics and topology of the polynomials drastically change. In such a context proving continuity is quite challenging while real analyticity will most likely break. Our approach will, on the one hand, build on the existing methods of proving continuity of Hausdorff dimension, primarily based on proving continuity, in the weak* topology of measures on the Riemann sphere, of canonical conformal measures, but will also require methods which, up to my best knowledge, have not been implemented anywhere yet. Our main result gives a surprising example where the Hausdorff dimension of the Julia set is continuous in the parameter, but where the Julia set itself is not.

We proved that the topological conjugacy relation on $T_1$, a subclass of Toeplitz subshifts, is hyperfinite, extending Kaya's result that the topological conjugate relation of Toeplitz subshifts with growing blocks is hyperfinite. A close concept about the topological conjugacy is the flip conjugacy, which has been broadly studied in terms of the topological full groups. Particularly, we provided an equivalent characterization on Toeplitz subshifts with single hole structure to be flip invariant.

In a stopping rule problem, a real-time player decides to stop or continue at stage n based on the observations up to that stage, but in a k-step look-ahead stopping rule problem, we suppose the player knows k steps ahead. The aim of this Ph.D. dissertation is to study this type of prophet problems for simple random walk, determine the optimal stopping rule and calculate the expected return for them. The optimal one-step look-ahead stopping rule for a finite simple random walk is determined in this work. We also study two infinite horizon stopping rule problems, sum with negative drift problems and discounted sum problems. The optimal one, two and three-step look-ahead stopping rules are introduced for the sum with negative drift problem for simple random walk. We also compare the maximum expected returns and calculate the upper bound for the advantage of the prophet over the decision maker. The last chapter of this dissertation concentrates on the discounted sum problem for simple random walk. Optimal one-step look-ahead stopping rule is defined and lastly we compare the optimal expected return for one-step look-ahead prophet with a real-time decision maker.

The structure and geometry of subspaces of a given Banach space is among the most fundamental questions in Functional Analysis. In 1961, Kadec and Pelczyński pioneered a field of study by analyzing the structures of subspaces and basic sequences in L_p[0,1] under a naturally occurring restriction of p, 2 < p <\infty. They proved that any infinite-dimensional subspace X\subset L_p[0,1] for 2<p<\infty must either be isomorphic to l_2 and complemented in L_p or must contain a complemented subspace which is isomorphic to l_p. Many works since have studied the relationships between the sides of this dichotomy, chiefly by weakening hypotheses on side of the equation to gain stronger assumptions on the other. In this way, Johnson and Odell were able to show in 1974 that if X contains no further subspace which is isomorphic to l_2, then it must embed into l_p. Kalton and Werner further strengthened this result in 1993 by showing that such an embedding must be almost isometric. We start by analyzing the tools and definitions originally introduced in 1961 and define a natural extension to these methods. By analyzing this extension, we provide a constructive and streamlined reproving of Kalton and Werner's theorem: Let X be …

In geometry we will consider n-dimensional generalizations of the Power of a Point Theorem and of Pascal's Hexagon Theorem. In generalizing the Power of a Point Theorem, we will consider collections of cones determined by the intersections of an (n-1)-sphere and a pair of hyperplanes. We will then use these constructions to produce an n-dimensional generalization of Pascal's Hexagon Theorem, a classical plane geometry result which states that "Given a hexagon inscribed in a conic section, the three pairs of continuations of opposite sides meet on a straight line." Our generalization of this theorem will consider a pair of n-simplices intersecting an (n-1)-sphere, and will conclude with the intersections of corresponding faces lying in a hyperplane. In graph theory we will explore the interaction between zero forcing and cut-sets. The color change rule which lies at the center of zero forcing says "Suppose that each of the vertices of a graph are colored either blue or white. If u is a blue vertex and v is its only white neighbor, then u can force v to change to blue." The concept of zero forcing was introduced by the AIM Minimum Rank - Special Graphs Work Group in 2007 as a …

Graded Hecke algebras are deformations of skew group algebras which arise from a group acting on a polynomial ring. Over fields of characteristic zero, these deformations have been studied in depth and include both symplectic reflection algebras and rational Cherednik algebras as examples. In Lusztig's graded affine Hecke algebras, the action of the group is deformed, but not the commutativity of the vectors. In Drinfeld's Hecke algebras, the commutativity of the vectors is deformed, but not the action of the group. Lusztig's algebras are all isomorphic to Drinfeld's algebras in the nonmodular setting. We find new deformations in the modular setting, i.e., when the characteristic of the underlying field divides the order of the group. We use Poincare-Birkhoff-Witt conditions to classify these deformations arising from the symmetric group acting on a polynomial ring in arbitrary characteristic, including the modular case.

In this dissertation we prove some results about the existence of families of Aronszajn trees on successors of regular cardinals which are pairwise not club isomorphic. The history of this topic begins with a theorem of Gaifman and Specker in the 1960s which asserts the existence from ZFC of many pairwise not isomorphic Aronszajn trees. Since that result was proven, the focus has turned to comparing Aronszajn trees with respect to isomorphisms on a club of levels, instead of on the entire tree. In the 1980s Abraham and Shelah proved that the Proper Forcing Axiom implies that any two Aronszajn trees on the first uncountable cardinal are club isomorphic. This theorem was generalized to higher cardinals in recent work of Krueger. Abraham and Shelah also proved that the opposite holds under diamond principles. In this dissertation we address the existence of pairwise not club isomorphic Aronszajn trees on higher cardinals from a variety of cardinal arithmetic and diamond principle assumptions. For example, on the successor of a regular cardinal, assuming GCH and the diamond principle on the critical cofinality, there exists a large collection of special Aronszajn trees such that any two of them do not contain club isomorphic subtrees.

In prophet problems, two players with different levels of information make decisions to optimize their return from an underlying optimal stopping problem. The player with more information is called the "prophet" while the player with less information is known as the "gambler." In this thesis, as in the majority of the literature on such problems, we assume that the prophet is omniscient, and the gambler does not know future outcomes when making his decisions. Certainly, the prophet will get a better return than the gambler. But how much better? The goal of a prophet problem is to find the least upper bound on the difference (or ratio) between the prophet's return, M, and the gambler's return, V. In this thesis, we present new prophet problems where we seek the least upper bound on M-V when there is a fixed cost per observations. Most prophet problems in the literature compare M and V when prophet and gambler buy (or sell) one asset. The new prophet problems presented in Chapters 3 and 4 treat a scenario where prophet and gambler optimize their return from selling two assets, when there is a fixed cost per observation. Sharp bounds for the problems on small …

The study of Borel equivalence relations on Polish spaces has become a major area of focus within descriptive set theory. Primarily, work in this area has been carried out using the standard methods of descriptive set theory. In this work, however, we develop a model-theoretic framework suitable for the study of Borel equivalence relations, introducing a class of objects we call Borel structurings. We then use these structurings to examine conditions under which marker sets for Borel equivalence relations can be concluded to exist or not exist, as well as investigating to what extent the Compactness Theorem from first-order logic continues to hold for Borel structurings.

We prove the existence and nonexistence of solutions for the semilinear problem ∆u + K(r)f(u) = 0 with various boundary conditions on the exterior of the ball in R^N such that lim r→∞u(r) = 0. Here f : R → R is an odd locally lipschitz non-linear function such that there exists a β > 0 with f < 0 on (0, β), f > 0 on (β, ∞), and K(r) \equiv r^−α for some α > 0.

In this dissertation we focus on the application of thermodynamic formalism to non-autonomous and random dynamical systems. Specifically we use the thermodynamic formalism to investigate the dimension of various fractal constructions via the, now standard, technique of Bowen which he developed in his 1979 paper on quasi-Fuchsian groups. Bowen showed, roughly speaking, that the dimension of a fractal is equal to the zero of the relevant topological pressure function. We generalize the results of Rempe-Gillen and Urbanski on non-autonomous iterated function systems to the setting of non-autonomous graph directed Markov systems and then show that the Hausdorff dimension of the fractal limit set is equal to the zero of the associated pressure function provided the size of the alphabets at each time step do not grow too quickly. In trying to remove these growth restrictions, we present several other systems for which Bowen's formula holds, most notably ascending systems. We then use these various constructions to investigate the Hausdorff dimension of various subsets of the Julia set for different large classes of transcendental meromorphic functions of finite order which have been perturbed non-autonomously. In particular we find lower and upper bounds for the dimension of the subset of the Julia …

For a dynamical system on a metric space a shrinking-target set consists of those points whose orbit hit a given ball of shrinking radius infinitely often. Historically such sets originate in Diophantine approximation, in which case they describe the set of well-approximable numbers. One aspect of such sets that is often studied is their Hausdorff dimension. We will show that an analogue of Bowen's dimension formula holds for such sets when they are generated by conformal non-autonomous iterated function systems satisfying some natural assumptions.

Crystallographic complex reflection groups are generated by reflections about affine hyperplanes in complex space and stabilize a full rank lattice. These analogs of affine Weyl groups have infinite order and were classified by V.L. Popov in 1982. The classical Braid theorem (first established by E. Artin and E. Brieskorn) asserts that the Artin group of a reflection group (finite or affine Weyl) gives the fundamental group of regular orbits. In other words, the fundamental group of the space with reflecting hyperplanes removed has a presentation mimicking that of the Coxeter presentation; one need only remove relations giving generators finite order. N.V Dung used a semi-cell construction to prove the Braid theorem for affine Weyl groups. Malle conjectured that the Braid theorem holds for all crystallographic complex reflection groups after constructing Coxeter-like reflection presentations. We show how to extend Dung's ideas to crystallographic complex reflection groups and then extend the Braid theorem to some groups in the infinite family [G(r,p,n)]. The proof requires a new classification of crystallographic groups in the infinite family that fail the Steinberg theorem.

Spaces such as the closed interval [0, 1] do not have the property of being homogeneous, strongly locally homogeneous (SLH) or countable dense homogeneous (CDH), but the Hilbert cube has all three properties. We investigate subsets X of real numbers to determine when their countable product is homogeneous, SLH, or CDH. We give necessary and sufficient conditions for the product to be homogeneous. We also prove that the product is SLH if and only if X is zero-dimensional or an interval. And finally we show that for a Borel subset X of real numbers the product is CDH iff X is a G-delta zero-dimensional set or an interval.

Credibility theory is widely used in insurance. It is included in the examination of the Society of Actuaries and in the construction and evaluation of actuarial models. In particular, the Buhlmann credibility model has played a fundamental role in both actuarial theory and practice. It provides a mathematical rigorous procedure for deciding how much credibility should be given to the actual experience rating of an individual risk relative to the manual rating common to a particular class of risks. However, for any selected risk, the Buhlmann model assumes that the outcome random variables in both experience periods and future periods are independent and identically distributed. In addition, the Buhlmann method uses sample mean-based estimators to insure the selected risk, which may be a poor estimator of future costs if only a few observations of past events (costs) are available. We present an extension of the Buhlmann model and propose a general method based on a linear combination of both robust and efficient estimators in a dependence framework. The performance of the proposed procedure is demonstrated by Monte Carlo simulations.

In the context of fractal geometry, the natural extension of volume in Euclidean space is given by Hausdorff and packing measures. These measures arise naturally in the context of iterated function systems (IFS). For example, if the IFS is finite and conformal, then the Hausdorff and packing dimensions of the limit sets agree and the corresponding Hausdorff and packing measures are positive and finite. Moreover, the map which takes the IFS to its dimension is continuous. Developing on previous work, we show that the map which takes a finite conformal IFS to the numerical value of its packing measure is continuous. In the context of self-similar sets, we introduce the super separation condition. We then combine this condition with known density theorems to get a better handle on finding balls of maximum density. This allows us to extend the work of others and give exact formulas for the numerical value of packing measure for classes of Cantor sets, Sierpinski N-gons, and Sierpinski simplexes.

Quantum Drinfeld Hecke algebras extend both Lusztig's graded Hecke algebras and the symplectic reflection algebras of Etingof and Ginzburg to the quantum setting. A quantum (or skew) polynomial ring is generated by variables which commute only up to a set of quantum parameters. Certain finite groups may act by graded automorphisms on a quantum polynomial ring and quantum Drinfeld Hecke algebras deform the natural semi-direct product. We classify these algebras for the infinite family of complex reflection groups acting in arbitrary dimension. We also classify quantum Drinfeld Hecke algebras in arbitrary dimension for the infinite family of mystic reflection groups of Kirkman, Kuzmanovich, and Zhang, who showed they satisfy a Shephard-Todd-Chevalley theorem in the quantum setting. Using a classification of automorphisms of quantum polynomial rings in low dimension, we develop tools for studying quantum Drinfeld Hecke algebras in 3 dimensions. We describe the parameter space of such algebras using special properties of the quantum determinant in low dimension; although the quantum determinant is not a homomorphism in general, it is a homomorphism on the finite linear groups acting in dimension 3.

Yokonuma-type Hecke algebras are a class of Hecke algebras built from a Type A construction. In this thesis, I construct the irreducible representations for a class of generic Yokonuma-type Hecke algebras which specialize to group algebras of the complex reflection groups and to endomorphism rings of certain permutation characters of finite general linear groups.

In this dissertation we study closure properties of pointclasses, scales on sets of reals and the models L[T2n], which are very natural canonical inner models of ZFC. We first characterize projective-like hierarchies by their associated ordinals. This solves a conjecture of Steel and a conjecture of Kechris, Solovay, and Steel. The solution to the first conjecture allows us in particular to reprove a strong partition property result on the ordinal of a Steel pointclass and derive a new boundedness principle which could be useful in the study of the cardinal structure of L(R). We then develop new methods which produce lightface scales on certain sets of reals. The methods are inspired by Jackson’s proof of the Kechris-Martin theorem. We then generalize the Kechris-Martin Theorem to all the Π12n+1 pointclasses using Jackson’s theory of descriptions. This in turns allows us to characterize the sets of reals of a certain initial segment of the models L[T2n]. We then use this characterization and the generalization of Kechris-Martin theorem to show that the L[T2n] are unique. This generalizes previous work of Hjorth. We then characterize the L[T2n] in term of inner models theory, showing that they actually are constructible models over direct limit of …

The “infrastructure” of quadratic fields is a body of theory developed by Dan Shanks, Richard Mollin and others, in which they relate “reduced ideals” in the rings and sub-rings of integers in quadratic fields with periodicity in continued fraction expansions of quadratic numbers. In this thesis, we develop cubic analogs for several infrastructure theorems. We work in the field K=Q(), where 3=m for some square-free integer m, not congruent to ±1, modulo 9. First, we generalize the definition of a reduced ideal so that it applies to K, or to any number field. Then we show that K has only finitely many reduced ideals, and provide an algorithm for listing them. Next, we define a sequence based on the number alpha that is periodic and corresponds to the finite set of reduced principal ideals in K. Using this rudimentary infrastructure, we are able to establish results about fundamental units and reduced ideals for some classes of pure cubic fields. We also introduce an application to Diophantine approximation, in which we present a 2-dimensional analog of the Lagrange value of a badly approximable number, and calculate some examples.

In the dissertation we study the C(K) spaces focusing on the case when K is countable compact and more specifically, the structure of C() spaces for < ω1 via special type of trees that they contain. The dissertation is composed of three major sections. In the first section we give a detailed proof of the theorem of Bessaga and Pelczynski on the isomorphic classification of C() spaces. In due time, we describe the standard bases for C(ω) and prove that the bases are monotone. In the second section we consider the lattice-trees introduced by Bourgain, Rosenthal and Schechtman in C() spaces, and define rerooting and restriction of trees. The last section is devoted to the main results. We give some lower estimates of the ordinal-indices in C(ω). We prove that if the tree in C(ω) has large order with small constant then each function in the root must have infinitely many big coordinates. Along the way we deduce some upper estimates for c0 and C(ω), and give a simple proof of Cambern's result that the Banach-Mazur distance between c0 and c = C(ω) is equal to 3.

Suppose that G is a finite, unitary reflection group acting on a complex vector space V and X is a subspace of V. Define N to be the setwise stabilizer of X in G, Z to be the pointwise stabilizer, and C=N/Z. Then restriction defines a homomorphism from the algebra of G-invariant polynomial functions on V to the algebra of C-invariant functions on X. In my thesis, I extend earlier work by Douglass and Röhrle for Coxeter groups to the case where G is a complex reflection group of type G(r,p,n) in the notation of Shephard and Todd and X is in the lattice of the reflection arrangement of G. The main result characterizes when the restriction mapping is surjective in terms of the exponents of G and C and their reflection arrangements.

A steepest descent method is constructed for the general setting of a linear differential equation paired with uniqueness-inducing conditions which might yield a generally overdetermined system. The method differs from traditional steepest descent methods by considering the conditions when defining the corresponding Sobolev space. The descent method converges to the unique solution to the differential equation so that change in condition values is minimal. The system has a solution if and only if the first iteration of steepest descent satisfies the system. The finite analogue of the descent method is applied to example problems involving finite difference equations. The well-posed problems include a singular ordinary differential equation and Laplace’s equation, each paired with respective Dirichlet-type conditions. The overdetermined problems include a first-order nonsingular ordinary differential equation with Dirichlet-type conditions and the wave equation with both Dirichlet and Neumann conditions. The method is applied in an investigation of the Tricomi equation, a long-studied equation which acts as a prototype of mixed partial differential equations and has application in transonic flow. The Tricomi equation has been studied for at least ninety years, yet necessary and sufficient conditions for existence and uniqueness of solutions on an arbitrary mixed domain remain unknown. The domains …