« There's Gold in Them Thar Campuses | Main | Yo ho ho and a bottle of jihad. »

August 18, 2005


D. Eppstein

I guess I must not be one of your human readers, because I think this stuff is fascinating. You can also immediately get a subquadratic algorithm from the decision tree result, by building a decision tree for a small enough problem and applying it separately to submatrices of the original nxn matrix of differences, but that seems to only save a log^{1/4}n factor compared to the full log in Timothy's approach.

On the other hand, I enjoy funny games with bits, so now I'm going to have to look at Erik's paper.

The comments to this entry are closed.