Channels ▼

Jonathan Erickson

Dr. Dobb's Bloggers

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

January 11, 2008

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.

Related Reading

More Insights

Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.