Every year, the Computing Research Association gives out awards for the best research done by undergraduates in North America. This year, my student Elyot Grant shared the top prize for males with Matt McCutchen from the University of Maryland.
Here are some of the problems Elyot worked on. First, he found a quadratic lower bound corresponding to a famous 1977 theorem of Entringer, Jackson, and Schatz that states that every binary string of length ≥ n2 + 6n contains an abelian square of order ≥ n. (An abelian square is two consecutive blocks where one is a permutation of the other; for example, reappear is an abelian square, as reap is a permutation of pear.)
Second, a problem of Alon and Spencer shows that for all ε > 0, there exists an infinite binary word such that any two consecutive blocks xx' of the same length t > N differ in at least (1/2 - ε)t positions. This raises the natural question, can the bound of (1/2 - ε) be replaced by a number > 1/2? Elyot proved the answer is no, using an extremely clever idea. This paper, co-written with my postdoc Thomas Stoll, appeared in the journal Acta Arithmetica.
Third, Elyot found beautiful results on “open” and “closed” languages, which are analogous to open and closed sets in topological spaces. His work with me and John Brzozowski was accepted for the DLT 2009 conference, and Elyot gave a beautiful talk on the subject.
So, congratulations to Elyot on this prestigious award!
