Notions of robust information-coding
University of Connecticut
We study several notions of computability-theoretic reducibility between subsets of natural numbers that are “robust” in the following sense: given a notion of largeness, a set $B$ is reducible to a set $A$ if every set that agrees with $A$ on a large domain uniformly computes a set that agrees with $B$ on a large domain. A familiar example is 1-reducibility, for which “large” can be taken to mean “cofinite”. This framework encompasses a wide range of reducibilities, including generic reducibility, for which “large” means “of density 1,” and which was first studied by Jockusch and Schupp. We obtain some new results concerning this reducibility, and introduce several related reducibilities that behave quite counterintuitively. For instance, infinite-information reducibility, for which “large” simply means “infinite”, enjoys the unusual property of admitting maximal pairs. I will discuss this and other results about these reducibilities, and sketch some of the techniques needed to prove them. This is joint work with Greg Igusa.
Damir Dzhafarov studies computability theory and reverse mathematics. He received his doctorate in 2011 from the University of Chicago, as a student of Profs. Robert Soare, Denis Hirschfeldt, and Antonio Montalban, and then held an NSF Postdoctoral Fellowship at Notre Dame University and at the University of California-Berkeley. In 2013 he joined the mathematics faculty of the University of Connecticut.