Computational Complexity

I am primarily interested in the NP problem (What is the power of nondeterminism?), the BPP problem (What is the power of randomness?), and complexity in analysis (especially geometric measure theory). I have developed three analytic tools for investigating these problems: These are complexity-theoretic generalizations of classical Baire category, Lebesgue measure, and Hausdorff dimension (fractal dimension), respectively. Each provides a mathematical means of quantifying the sizes of subsets of various complexity classes.

In recent years, many investigators have worked with these tools, extending them and using them to shed new light on a wide variety of topics in computational complexity. I enjoy being a part of this ongoing effort.


John Hitchcock maintains online bibliographies on resource-bounded measure and effective fractal dimensions, with links to available papers in the latter.