Rather than spending much time blogging about SODA today, I spent the time instead updating the Wikipedia article on Davenport–Schinzel sequences with Gabriel Nivasch's new and very nice results tightening the bounds for the order-3 and even-order cases of these sequences.

Gabriel deservedly won the best student paper award at SODA for these results, a preprint of which can be found at arXiv:0807.0484.

Given how efficiently I was corrected about the mistake I made in yesterday's post (I had given a too-large time bound for the planar Steiner tree PTAS, now fixed I hope), I hope any necessary corrections to these edits will be equally efficient.