Recent Preprints

	Randomness Notions and Partial Relativization with Joe Miller and Andre Nies
	Abstract: We study weak 2 randomness, weak randomness relative to $0'$ and Schnorr randomness relative to $0'$. One major theme is characterizing the oracles $A$ such that $\ML[A]\sub \mathcal C$, where $\mathcal C$ is a randomness notion and $\ML[A]$ denotes the Martin-Lof random reals relative to $A$. We discuss the connections with $LR$-reducibility and also study the reducibility associated with weak $2$-randomness. Format:
	Tracing and domination in the Turing degrees
	Abstract: We show that if $0'$ is c.e. traceable by $a$, then $a$ is array non-computable. It follows that there is no minimal almost everywhere dominating degree, in the sense of Dobrinen and Simpson. This answers a question of Simpson and a question of Nies. Also it gives a natural definable property, namely non-minimality, which separates almost everywhere domination from highness. Format:
	Elementary differences between the degrees of unsolvability and degrees of compressibility
	Abstract: Given two infinite binary sequences $A$, $B$ we say that $B$ can compress at least as well as $A$ if the prefix-free Kolmogorov complexity relative to $B$ of any binary string is at most as much as the prefix-free Kolmogorov complexity relative to $A$, modulo a constant. This relation, introduced by Nies and denoted by $A \leq_{LK} B$, is a measure of relative compressing power of oracles, in the same way that Turing reducibility is a measure of relative information. The equivalence classes induced by $\leq_{LK}$ are called LK degrees (or degrees of compressibility) and there is a least degree containing the oracles which can only compress as much as a computable oracle, also called the "low for K" sets. A classic result from of Nies states that these coincide with the K-trivial sets, which are the ones having minimal prefix-free Kolmogorov complexity. We show that with respect to $\leq_{LK}$, given any non-trivial $\Delta^0_2$ sets $X,Y$ there is a computably enumerable set A which is not K-trivial and it is below $X,Y$ . This shows that the local structures of $\Sigma^0_1$ and $\Delta^0_2$ Turing degrees are not elementarily equivalent to the corresponding local structures in the LK degrees. It also shows that there is no pair of sets computable from the halting problem which forms a minimal pair in the LK degrees; this is sharp in terms of the jump, as it is known that there are sets computable from $0''$ which form a minimal pair in the LK degrees. We also show that the structure of LK degrees below the LK degree of the halting problem is not elementarily equivalent to the $\Delta^0_2$ or $\Sigma^0_1$ structures of LK degrees. The proofs introduce a new technique of permitting below a $\Delta^0_2$ set that is not K-trivial, which is likely to have wider applications. Format: