Friday, December 29, 2006

Howdy, neighbor

Constructing phylogenetic trees from distances is crucial to computational genomics. That's why this paper is such a comfort; R. Mihaescu, D. Levy, and L. Pachter have shown that the neighbor-joining algorithm accomplishes this task very quickly, at least in an asymptotic and probabilistic sense.

I once overheard the third author wish to see his website at the top of the list of Liors. Back then he was fourth, as of this writing, he's made his way to the number two spot. I'm willing to do my part to help his dream become reality.

Friday, December 22, 2006

In the shadow of Sun

You know you live in Silicon Valley when your employer is on the same exit as campuses for Yahoo! and Sun.

Wednesday, December 20, 2006

Familiar territory

See, set theory is easy!

Friday, December 15, 2006

Recursion is child's play

Every mathematician (and almost everyone, in fact) is familiar with the "Tower of Hanoi" problem. Not only is it a great way to occupy a patient child for a while, it provides a wonderful illustration of the twin concepts of recursion and induction in the description of the solution to the n-disk problem and the expression of the minimum number of steps in the optimal solution, respectively.

But what if the moves were restricted beyond the basic three commandments? (Thou shalt not place a disk atop any disk of smaller size, for it is hateful to do so; and Thou shalt not place thy hand on more than one disk at the one time, lest you succumb to greed and avarice; and Thou shalt not try to weasel thy way around that last commandment by lifting a disk that is not topmost on its peg, what kind of fool do you take me for?) If, in addition, there is a bound on the difference between the sizes of adjacent disks, what is the optimal solution (if there is one) and how many moves does it take? S. Bendetkis and I. Safro have written a paper dealing with precisely this generalization of the classic problem.

It's always a joy to see some good math on such familiar puzzles.

Wednesday, December 13, 2006


The three authors I mentioned recently for completing my work on doubly-laced crystals have put another paper on the arXiv, this time using their framework to unravel some fascinating properties of An-crystals.

A special prize awaits the first to explain the title of this post in a comment!

Saturday, December 09, 2006

Part of an RC graph

Also known as a pipe dream. While clearly not what the original designers had in mind for these tiles, this arrangement creates a beautiful rhythm, and could even be used in Schubert geometry.

Friday, December 08, 2006

Divide and be conquered

When I first read about J. Anderson's new theory of diving by zero, I was skeptical. There are numerous algebraic tricks one can play to make zero-division work out, and I would be surprised to see a novel approach to this problem so late in the game. After seeing the details of the "theory", I knew it was garbage, and suspected that it had already been dissected by M. Chu-Carroll at Good Math, Bad Math; lo and behold, it had.

In true ScienceBlogs form, Chu-Carroll pumps much more vitriol into his response than I would have. Rather than pushing my bile to the surface, it simply makes me wonder why Anderson would make such a foolhardy public display of his "discovery" without first consulting a working mathematician. England has no shortage of universities; they can't all be inaccessible from Berkshire.

Wednesday, December 06, 2006

Another shot at the travelling salesman problem

H. Kleiman has written a (very short) paper in which he claims to have proven that P=NP. Many of the usual red flags are up; e.g., his article is only available as a pdf (i.e., he provides no LaTeX source) and the references are light. On the other hand, he withholds the usual bluster with which such claims are made, instead using language like "we (hopefully) can always obtain an optimal tour in M(a) in polynomial time" and "[i]f the algorithm has no errors, ... P=NP." Time will tell...

Tuesday, December 05, 2006

SECANTS RATE highly in my book

Longtime readers already know that I'm a regular visitor to to get the daily comic by R. Stevens (or rstevens, as he prefers) featuring the inimitable Clango Cyclotron. He really should visit LBL at some point and see some of the ARCANE TESTS they carry out with the 88". You know, Clango could get in touch with his roots; after all, that first 'L' stands for Lawrence, the inventor of the cyclotron.

I'm enough of a fan of DS that I got my lovely wife a t-shirt featuring a punchline from the comic for Christmas last year. Being a mammalogist, this is far and away the most appropriate of the DS shirts for her to wear, although our CAT RESENTS A message so positive about another species.

I get the impression that R. Stevens is a cat person (and Mac user) like me; given the opportunity, I would CARESS TEN, AT least.

A wish of mine has been granted, and some recent Diesel Sweeties strips have featured mathematically-themed humor. It's good to see that R. Stevens RECASTS A NET from time to time to trawl for these sorts of jokes. The second, in addition to referencing one of the great integer sequences, is concerned with puns, which mathematicians inexplicably enjoy more than most other people. Some mathematicians also enjoy anagrams, although that's more easily explained by the fact that they are a special case of permutations.

To celebrate cope with the commerce season, Stevens is running an anagrammatically named contest. He's a rather good sport about it, even suggesting that writers might describe his pants as a one-ACRE ASS TENT. If I were to open myself up to such public conversation, I'd feel like an ANT AT RECESS, leaving myself completely at the whim of schoolkids. I like his output too much to be so cruel; I especially enjoy Maura's antics (A TART'S SCENE if ever there was one) and the strips in which A SCAT ENTERS. I usually detest "bio-humor", but somehow Stevens treats it so absurdly that it has a certain appeal.

Here's wishing R. Stevens, Clango, and the whole Diesel Sweeties crew a Merry Present Season and a Happy New Year!