Ph.D. Recipients and their Thesis Abstracts

Logic

Algebra, Analysis, Combinatorics, Differential Equations / Dynamical Systems, Differential Geometry, Geometry, Interdisciplinary, Lie Groups, Logic, Mathematical Physics, PDE / Numerical Analysis, Probability, Statistics, Topology

A Theory of Multitask Learning for Learning from Disparate Data Sources

Abstract: Many endeavors require the integration of data from multiple data sources. One major obstacle to such undertakings is the fact that different sources may vary considerably in the way they choose to represent their data, even if their data collections are otherwise perfectly compatible. In practice, this problem is usually solved
by a manual construction of translations between these data representations, although there have been some recent attempts at supplementing this with automated algorithms based on machine learning methods.

This work addresses the problem of making classification predictions based on data from multiple sources, without constructing explicit translations between them. We view this problem as a special case of the problem of multitask learning: Both intuition and much empirical work indicate that learning can be improved by attacking multiple related tasks simultaneously; however, thus far, no theoretical work has been able to support this claim, and no concrete definition has been proposed for what it means for two learning tasks to be "related."

In this work, we introduce a general notion of relatedness between tasks, provide the standard sort of information complexity bound for learning such tasks, and give general conditions under which this bound is an improvement over the standard single task learning result.

Finally, we apply these results to the problem of learning from disparate data sources. We give a decision tree learning algorithm for this problem for a particular type of data source disparity and demonstrate its empirical success on real data sets.

Pi-0-1 Classes in Computable Analysis and Topology

Abstract: We explore aspects of \Pi^0_1 classes in R^n. These are the effective closed sets of computable analysis and natural analogs of the \Pi^0_1 classes in 2^\omega, widely studied by computability theorists. In Chapter II, we characterize the fixable classes—the sets of fixed point of computable maps from the unit cube [0,1]^n to itself—as the \Pi^0_1 classes which contain a nonempty, connected \Pi^0_1 subclass. This settles a question asked in Cenzer and Jockusch (2000). To prove that Brouwer's theorem is inconsistent with Russian constructivism, Orevkov gave a fixable class with no computable points (1963). Our proof employs a generalization of Orevkov's construction, as well as the notion of topological degree. Homology theory is used in the definition and computation of the topological degree. Homology returns in Chapter III, where chains are used to take algorithmic advantage of the topological structure of a \Pi^0_1 class. We show that a \Pi^0_1 class homeomorphic to a sphere is located: the distance to the class is computable. Closed balls embedded as \Pi^0_1 classes are also studied. Chapter IV studies members of \Pi^0_1 classes which contain no computable points. These avoidable points were introduced by Kalantari and Welch. Avoidability is a type of effective non-computability; we introduce hyperavoidability, a stronger notion, and initiate the computability theoretic study of both classes, including their behavior in the Turing and weak truth-table degrees.

Effective Completeness Theorems for Modal Logics

Abstract: We initiate the study of computable model theory of modal logic, by establishing effective completeness theorems for a variety of modal logics. For each of the logics we consider, we give a natural definition of a decidable Kripke model, and then show how to construct such a decidable Kripke model of a given decidable theory.

Our new technique of constructing Kripke models is inspired by the Henkin construction for classical logic. The Henkin construction, however, depends in an essential way on the Deduction Theorem. In its usual form the Deduction Theorem fails for modal logic. In our constructions, the Deduction Theorem is replaced by a result about objects called finite Kripke diagrams. We give an argument that this result can be viewed as an analogue of the Deduction Theorem for modal logic.

We prove effective completeness theorems for the following modal logics:

• Constant domain first-order modal logic with the Box and Diamond modalities, initially with no restriction on the possibility relation (i.e., the logic K).
• Logics corresponding to special possibility relations: T, K4, K5, S4, S5.
• Two generalizations of constant domains for first-order modal logic: varying domains and monotonic domains.
• Propositional modal logics which contain "infinitary" modalities: temporal logic, epistemic logic, and dynamic logic.

Characterizations for Computable Structures

Abstract: A major theme in computable model theory is the study of necessary and sufficient conditions for the existence of certain types of computable structures. These characterizations may either be syntactic, as in the work of Millar [36], or semantic, as in the work of Goncharov [16]. Presented in this dissertation is a general framework for proving syntactic characterizations for the existence of computable models of various theories. This framework is used to show that an axiomatizable \forall_2 theory has a computable, existentially closed model if and only if it has an existentially conservative 1-completion for which the set of universal theorems is decidable. Several other uses of this framework are given; one answers an open question of Baldwin and Kueker [4] in the classical model theory of existentially closed, algebraically prime models. Semantic characterizations of computable structures are also investigated. By analyzing the computational complexity of various classes of computable structures, it is shown that various model theoretic properties have no essentially simpler characterization. For example, it is shown that the classes of computable homogeneous structures, computable atomic structures, and computable computably saturated structures are all \Pi^0_{\omega+2}-complete. Other results include the fact that the class of hyperarithmetically categorical structures is \Pi_1^1-complete, and that the set of computably categorical structures is \Pi^0_4-hard.

Degree Spectra of Relations on Computable Structures

Abstract: The study of additional relations on computable structures began with the work of Ash and Nerode. The concept of degree spectra of relations was later introduced by Harizanov. In this dissertation, several new examples of possible degree spectra of relations on computable structures are given. In particular, it is shown that, for every c.e. degree a, the set {0,a} can be realized as the degree spectrum of an intrinsically c.e. relation on a structure of computable dimension two, thus answering a question of Goncharov and Khoussainov. Some extensions of this result are given, and the methods used in proving it are employed to construct a computably categorical structure whose expansion by a single constant has computable dimension \omega. Degree spectra of relations on computable models of particular algebraic theories are also investigated. For example, it is shown that, for every n > 0, there is a computable integral domain with a subring whose degree spectrum consists of exactly n c.e. degrees, including 0. In contrast to this result, it is shown, for instance, that the degree spectrum of a computable relation on a computable linear ordering is either a singleton or infinite. In both cases, sufficient criteria for similar results to hold of a given class of structures are provided.

Nonmonotonic Logic: A Monotonic Approach

Abstract: We present a monotone inductive characterization of the set of skeptical consequences of a nonmonotonic rule system. Nonmonotonic rule systems are an abstraction of the nonmonotonic properties of many systems designed to formalize everyday reasoning, including default logic, autoepistemic logic, and logic programming. We begin with preliminary results about nonmonotonic rule systems and continue by showing their mutual translatability with several other standard nonmonotonic logics. The main result is the soundness and completeness of a tableau proof system (using countably branching tableaux) for skeptical consequence. We conclude by using the tableau result to generate several other monotone proof systems, including a sequent calculus and an axiomatization of skeptical consequence in L_{\omega_1 \omega}.

Reverse Mathematics and Ordered Groups

Abstract: We study theorems of ordered group theory from the viewpoints of reverse mathematics and computable mathematics. Reverse mathematics uses subsystems of second order arithmetic to determine which set existence axioms are required to prove particular theorems. We give equivalences of WKL_0 (the orderability of direct products and nilpotent groups, the classical semigroup conditions for orderability), ACA_0 (the existence of induced orders on quotient groups, the existence of the center of a group) and \Pi_1^1 – CA_0 (the classification of order types for countable fully ordered abelian groups). We show that RCA_0 suffices to prove Hölder's Theorem and the theorem that every ordered group is the quotient of an ordered free group by a convex normal subgroup. In computable mathematics, we examine the complexity of orders on computable abelian and nilpotent groups and we study the relationship between spaces of orders of computable groups and computably bounded \Pi_1^0 classes. Finally, we show that every orderable computable abelian group has a computable presentation with a computable order. This work answers several open questions from Downey and Kurtz (1986).

Modal Logics for Continuous Dynamics

Abstract: This work is a formal investigation of a number of bimodal and polymodal logics built on a base of propositional S4, and is a contribution to the theory of hybrid control systems. It is the first stage of a larger project of developing logics for the design and verification of such systems. A hybrid control system is a network of finite-state digital machines which act on and react to a dynamically changing environment, where such environments may have mixed analog and digital states. Following Nerode, I look to topology to provide a mediating link between the analog and digital worlds; S4 is taken as a logical foundation since from Tarski and McKinsey, it is the logic of topology.

The base logic S4F adds to the \square (topological interior) of S4 a modality [a] for representing the effect of an action in an environment; [a] is interpreted by a total function. In this logic, the continuity of a function with respect to a topology is expressible. In the second stage of this study, a fragment of deterministic propositional dynamic logic DPDL is overlaid on S4F to produce a new modal dynamic logic. In the resulting logic, called TPDL (topological propositional dynamic logic), atomic actions are interpreted by continuous functions, and complex actions are formed under the Kleene operations of composition, choice and iteration.

Both a Tarski-style topological semantics and a Kripke semantics are presented for the logics. Building on work of Grzegorczyk, I identify a subclass of topological structures naturally dual to Kripke frames. Topologies in this class are such that every point is contained in a smallest open set. As argued by Nerode, these are precisely the topologies needed to give an account of analog-to-digital conversion.

In addition to Hilbert-style axiomatizations, tableaux proof systems are presented for each of the logics and proved complete. The tableaux completeness proofs construct countable T_0 topologies whose elements are functional terms, in which the term constructor functions are continuous. Finite quotients of the term model are obtained, so establishing the decidability of each of the logics.

Priority Methods and Fragments of Arithmetic

Abstract: We take Lempp and Lerman's iterated tree framework as a description of the general 0^(n)-priority method and prove that the general 0^(n)-priority method succeeds if and only if I\Sigma_n holds. We then apply this framework to get a uniform treatment of finite injury argument. We also prove that the existence of a high incomplete r.e. set does not imply I\Sigma_2. The main result of this thesis gives us an example of a theorem about the ordering of r.e. Degrees can be proved in P^– + I\Sigma_3, but not in P^– + B\Sigma_3.

Degrees of Random Sets

Abstract: An explicit recursion-theoretic definition of a random sequence or random set of natural numbers was given by Martin-Löf in 1966. Other approaches leading to the notions of n-randomness and weak n-randomness have been presented by Solovay, Chaitin, and Kurtz. We investigate the properties of n-random and weakly n-random sequences with an emphasis on the structure of their Turing degrees.

After an introduction and summary, in Chapter II we present several equivalent definitions of n-randomness and weak n-randomness including a new definition in terms of a forcing relation analogous to the characterization of n-generic sequences in terms of Cohen forcing. We also prove that, as conjectured by Kurtz, weak n-randomness is indeed strictly weaker than n-randomness.

Chapter III is concerned with intrinsic properties of n-random sequences. The main results are that an (n+ 1)-random sequence A satisfies the condition A^{(n)} \equiv_T A \oplus 0^{(n)} (strengthening a result due originally to Sacks) and that n-random sequences satisfy a number of strong independence properties, e.g., if A \oplus B is n-random then A is n-random to B. It follows that any countable distributive lattice can be embedded in the 2-random degrees. We also prove that, surprisingly, this independence property fails for weak n-randomness.

In Chapter IV we consider a number of known measure-theoretic results of the form "almost every degree has property P," and use the hierarchy of n-randomness to analyze "how much" randomness is needed for a given property to hold. We obtain fairly sharp results for most of the known properties. For example, Kurtz showed that a.e. Degree has a 1-generic predecessor and is relatively r.e. We analyze both proofs to show that 2-randomness is sufficient. That 1-randomness is not enough follows from a new "basis" theorem: every nonempty \prod^0_1-class contains a member with no relatively r.e. predecessor.

The notion of "almost every" degree and the explicit definitions of randomness we use depend on the measure employed. We conclude by proving a series of results concerning the invariance of the n-randomness degrees with respect to changes in this measure.

Last modified: February 11, 2004