Visiting Assistant Professor
B.A., Brandeis University, 2005
Ph.D., University of California, Berkeley, 2013
Office: 128 Hayes-Healy Hall
Phone: (574) 631-97131
Fax: (574) 631-6579
For additional information see Gregory Igusa’s Personal Page.
My research is in recursion theory, also known as computability theory. Specifically, most of my work has been focused around generic computations and generic reductions. I also enjoy working with other atypical notions of reducibility, and I am interested in effective and reverse mathematical combinatorics, especially work concerning partial orders.
Generic computation derives its name from complexity theory, where a given problem can sometimes be shown to be more complex in the generic case than it is in the worst case. So, to generically compute a real is to provide a computation of that real that halts on most inputs (in the sense of limiting density 1) and that always gives correct answers when it does halt. A generic reduction is a generic computation in which your oracle, similarly, does not always give answers when it is asked questions.
The Turing degrees embed into the generic degrees, and this embedding provides an interesting perspective from which to view the generic degrees: A Turing degree is hyperarithmetically computable if and only if it embeds below the generic degree of a set with limiting density 1. Also, there exist a large number of quasi-minimal degrees: degrees which are not upper bounds for any embedded Turing degrees, and which, therefore, do not have any information content, at least in the traditional sense of recursion theory. (Such degrees should be familiar to those who work with enumeration reductions.)
Gregory Igusa, Nonexistence of Minimal Pairs for Generic Computability. To appear
in J. Symbolic Logic, see also http://arxiv.org/abs/1202.2560.
Please direct questions and comments to: email@example.com