Saturday, October 22, 2005

Strange things happen

Around this time last year I was busy preparing my applications to PhD programs in the U.K. and North America. In particular, University of Cambridge, which happened to be one of those universities I was interested in , requires each applicant to write a short research proposal. [As you of course know, I chose University of Toronto, which was my first preference all along.] So, I had a discussion with Anuj Dawar, who was the finite model theorist at Cambridge I wished to work with, on what sort of research directions to pursue for PhD studies. He gave me two research problems:

  1. Homomorphism preservation theorem in the finite.
  2. Do order-invariant FO properties have the zero-one law?

Don't worry if you don't know what they mean. The important thing to know is that both of these problems are long-standing open problems in the area. Both of these problems looked formidable to me then (and they still do now), and so I didn't bother thinking about them. Anyway, to my surprise, both of these problems have been resolved this year in quick succession. The first problem was solved positively by Benjamin Rossman, who this year just started his graduate school. His paper titled

Existential Positive Types and Preservation Under Homomorphisms

was recently published in this year's LICS proceeding and awarded Kleene's award for the best student paper. [Congratulation Ben!] You can find his paper on his web site. The second problem was very recently solved by Leonid Libkin, my supervisor. You have to wait if you want to get the paper.

I wish I had collaborated with these guys on these problems. D'oh!


David Molnar said...

Hindsight is always 20/20. Besides, do you know that you would have been able to collaborate with these people, or that you would have found the right insight?

ben rubinstein said...

David is of course right. I'd also add that on the good side this says positive things about your new supervisor!

twidjaja said...

I have known of Ben Rossman (he solved another open problem in 2003) for a while, and have recently exchanged some emails. On the other hand, I have known my supervisor since last June. In conclusion, I could have worked with these people earlier! Only that I didn't know they were working on these problems. As far as finding the right insight ...

Of course, Ben's right. The bright side is that I am currently working with my supervisor.