Thursday, September 07, 2006

The Haystack

Derandomizing an RP algorithm is like finding hay in a haystack. In that vein comes the following cartoon from the Danish paper Politiken (via Peter Bro Miltersen).

Haystack: What's with you people? Why are you all obsessed with that stupid little thing!? What about wonderful me!? Love me! Give me love!
Caption: The haystack is upset that the needle gets all the attention.


  1. Looooool. I like this one a lot.
    I guess that this joke applies to many other things in CS as well...

    What about the worst case in the role of the needle, and the performance on all the other instances (on average, in practice, in smooth analysis, ....) as the haystack? The theoretician looks for the needle (P vs NP for worst case analysis for instance) while each practician looks in his own part of the haystack...

  2. Accepted papers in SODA'07 available at: