PhD Defenses

I have been thinking PhD defenses recently. Two of my students (Vlad, Irina) finished theirs and another (Yihua) will finish within a month. They will work in corporate labs (AT&T, Google, Google, resp).

At Copenhagen, I was on the PhD Committee when Philip Bille defended his thesis the past Thursday. Philip worked on hard problems (regular expression matching, tree matching and others) and eked out interesting improvements. In particular, he got improved space bounds in cases where dynamic programming has been the norm. It is reassuring that there are classical problems still lingering out there and that PhD students can, do and will study them.

Regex matching: we should nail down a faster algorithm for regex matching, a faster approximate algorithm, or simply show some hardness results since general lower bounds are too much to hope for? Testing regular languages is doable, but we don't have even remotely interesting approximate algorithms. Maybe show a reduction from matrix multiplication to regular expression recognition with a suitable encoding?