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!
8 comments:
Fantastic
Jeffrey, I want to thank you for your blog and much of the work you have done explaining information theory and how it relates to evolution. The internet is becoming increasingly full of religious apologists making these lists of bogus claims;
- evolution can not produce "new information"
- information only comes from a mind/intelligence
It is not simply a case of pointing out the flaws in these arguments to these people, it requires complete removal of a whole series of erroneous ideas from their minds that they are convinced are true. I just came across this on youtube where this guy manages to reel off a whole series of these canards in just a matter of minutes - http://www.youtube.com/watch?v=x2iZHCBMN1Y
This is what happens when people have their brains filled with nonsense by Meyer and Demsbki, without ever checking to see what actual credentialled scholars in these areas make of their claims.
shared the top prize for males
The prizes are sexually segregated?
Yes, there are prizes for males and females - as you'd see if you click on the link.
Jeff,
Congratulations!
Deane
Congrats to you and Elyot.
Second, a problem of Alon and Spencer...
I suppose this means for all N?
Do you have a preprint of this paper? I can't access Acta Arithmetica and can't find the paper on your website.
I suppose this means for all N?
No - N depends on epsilon. Then the result holds for all t > N.
If you send me e-mail reminding me of your address, I'll send you a copy.
Post a Comment