This dissertation consists of the proof of a single main result linking geometric ideas from the first-order model theory of infinite structures with complexity-theoretic analyses of problems over classes of finite structures. More precisely, we show that for a complete finite-variable theory of finite structures, models are efficiently recoverable from elementary diagrams if and only if the theory is super-rosy. In the course of the argument, we reconstitute the machinery of \th-independence and rosiness for classes of finite-structures, as well as a characterization of rosy classes analogous to the Independence theorem for the simple theories. We show that a super-rosy theory admits a weak form of model-theoretic coordinatization, which can be converted into to an algorithm for the model-building problem mentioned above in a natural and intuitive way. Conversely, we show how to extract a model-theoretic independence relation directly from an efficient algorithm for the model-building problem.

A split of an r.e. set A is a pair of disjoint r.e. sets whose union is A. We investigate information theoretic properties of r.e. sets and properties of their enumerations, and whether these properties are preserved under splittings. The first part is involved with dynamic notions. An r.e. set is speedable if for every computable function, there exists a finite algorithm enumerating membership faster, by the desired computable factor, on infinitely many integers. Remmel (1986) asked whether every speedable set could be split into two speedable sets. Jahn published a proof, answering their question positively. However, his proof was seen to be incorrect and we construct a speedable set that cannot be split into speedable sets, answering their question negatively. We also prove additional splitting results related to speedability.

The second part is involved with effectively closed sets. We introduce the notion of being recursively avoiding and prove several results.

We study viscosity solutions of the partial differential equation $$- \Delta_\infty u = f \quad \mbox{in } U,$$ where $U \subseteq \R^n$ is bounded and open, $f \in C(U) \cap L^\infty(U)$, and $$\Delta_\infty u := |Du|^{-2} \sum_{ij} u_{x_i} u_{x_i} u_{x_i x_j}$$ is the {\em infinity Laplacian}.

Our first result is the Max-Ball Theorem, which states that if $u \in USC(U)$ is a viscosity subsolution of $$- \Delta_\infty u \leq f \quad \mbox{in } U$$ and $\ep > 0$, then the function $v(x) := \max_{\bar B(x,\ep)} u$ satisfies $$2 v(x) - \max_{\bar B(x,\ep)} v - \min_{\bar B(x,\ep)} v \leq \max_{\bar B(x,2 \ep)} f,$$ for all $x \in U_{2\ep} := \{ x \in U : \dist(x, \partial U) > 2\ep \}$. The left-hand side of this latter inequality is a monotone finite difference scheme that is comparatively easy to analyze. The Max-Ball Theorem allows us to lift results for this finite difference scheme to the continuum equation. In particular, we obtain a new proof of uniqueness of viscosity solutions to the Dirichlet problem when $f \equiv 0$, $\inf f > 0$, or $\sup f < 0$. The results mentioned so far are joint work with S. Armstrong.

The Max-Ball Theorem is also useful in the analysis of numerical methods for the infinity Laplacian. We obtain a rate of convergence for the numerical method of Oberman \cite{MR2137000}. We also present a new adaptive finite difference scheme.

We also prove some results in Model Theory. We study rank-preserving interpretations of theories of finite Morley rank in strongly minimal sets. In particular, we partially answer a question posed by Hasson \cite{MR2286641}, showing that definable degree is not necessary for such interpretations. We generalize Ziegler's fusion of structures of finite Morley rank \cite{MR2441382} to a class of theories without definable degree. Our main combinatorial lemma also allows us to repair a mistake in \cite{MR2354912}.