Math research: all fun and games?

Wherein we try to illustrate by an example what research into pure mathematics is, and how it fits in with teaching of courses and applying for grants

In a small class project for MATH 301 (Discrete Mathematics, taught by Prof. Kjos-Hanssen) in Spring 2009, students studied a notion of automatic complexity of a sequence of zeros and ones.

Play the Complexity Guessing Game

This is a miniature version of the notion of Kolmogorov complexity.
A computer program written by three students in the class calculated the complexity of all such sequences of length at most 7.
The perhaps most interesting finding was that the string $011100$ is the only string of length $6$ or less whose complexity is increased when read backwards.
That is, 001110 is more complicated than 011100.

Pictured: a finite state automaton which only accepts one string of length 22, namely 0100011001010101111100, and which has 10 states. We say that this automaton is a witness to the fact that the string 0100011001010101111100 has automatic complexity at most 10.

  • This project was continued by Master’s student Kayleigh Hyde, who graduated in 2013. Hyde and Kjos-Hanssen wrote a paper on this subject which was accepted for publication
    and presented by Hyde at the conference COCOON (International Computing and Combinatorics Conference) in Atlanta, Georgia, in August 2014.
  • In September 2014 Prof. Kjos-Hanssen was awarded a five-year grant from the Simons Foundation, also entitled “Automatic Complexity”, to continue this research in collaboration with other mathematicians. This grant is part of the grant program Collaboration Grants for Mathematicians.

This line of development from 2009 to 2014 is an example of vertical integration of all levels from beginning undergraduate work, through graduate theses, to externally funded research.

In a new project, Prof. Kjos-Hanssen investigates the use of so-called structure functions for automatic complexity to statistically analyze data. For example, the most statistically significant fact about a string such as 0000000010000000100, from an automatic point of view, may be the fact that it contains exactly two 1s. The precise number of 0s that occurs may be relatively insignificant. The theory of structure functions makes this intuitive idea precise.

This story was presented in a general audience to the Dean’s Office of the College of Natural Sciences on May 5. View the slides

Play the Complexity Option Game