Accidental Algorithms, Or Do We Have Time for Another Cup of Coffee?Accidental Algorithms, Or Do We Have Time for Another Cup of Coffee?

Always one for a cup of joe, it was the headline "coffee-break criterion" that led me to stop and read Brian Hayes' article Accidental Algorithms in the current issue of American Scientist. You know what the coffee-break criterion is, right? According to Brian "a computation is slow if it's not finished when you come back from a coffee break." Clearly Brian has never gone on a coffee break with me.

But the point of Brian's article isn't coffee, tea, and most certainly not me. Rather it is about holographic (or "accidental") algorithms, which are a relatively recent phenomenon in computational mathematics. Invented by Leslie Valiant and described in his paper of the same name, holographic algorithms are "a new kind of reduction that allows for gadgets with many-to-many correspondences, in which the individual correspondences among the solution fragments can no longer be identifed. Their objective may be viewed as that of generating interference patterns among these solution fragments so as to conserve their sum." Valiant adds that "their computational power comes from the mutual cancellation of many contributions to a sum, as in the optical interference pattern that creates a hologram." Got that? In otherwords, holographic algorithms deal with the boundary that exists between easy and hard (NP) problems.

As for the "accidental" part, Brian Hayes explains that Valiant "refers to them as 'accidental algorithms,' emphasizing their capricious, rabbit-from-the-hat quality; they seem to pluck answers from a tangle of unlikely coincidences and cancellations."

Don't worry, I'm not going to attempt provide in this limited space a complete summary of what holographic (call me "accidental") algorithms are. It wouldn't be justice to Hayes, Valiant, or the algorithm. And in any event, I'm not smart enough to summarize it in 25 words or less. But don't shy away from Brian's article. It is interesting and likely important to a familiar class of problems.