Friday, November 30, 2007

2008 Election Correctly Predicted

Three European scientists have produced a document which correctly states who will win the 2008 US presidential election.

They don't need to give you the document (although they do) because they can give you the MD5 checksum. A checksum, which is a kind of fingerprint for the document, accordingly to the conventional wisdom can only come from that one document. In principle, other documents may exist with the same fingerprint, but are technically infeasible to find. Then, after the election is over, they will make the PDF available and invite you to measure its MD5. If it matches, that proves it has to have been the same one they fingerprinted back in Nov 30, 2007.

The fingerprint analogy goes pretty far. Imagine that they had said,
We know who will win the 2008 presidential election. To prove it, we found someone with his name and fingerprinted him. Here's the fingerprint ....

On the morrow of Election day, the person will visit your house, let you take his fingerprints and show his driver's license to prove his name is that of the person who won.


The catch, of course if that MD5s aren't really as good as fingerprints, despite widespread belief, even among experts. Marc Stevens, Arjen Lenstra and Weger have simply found an appealing way to exploit duplicatability of MD5s, constructing 12 documents with the same MD5, each with the name of different candidate (and some non-candidates). In our metaphor, this is coming up with 12 different people named after the candidates and then bioengineering them to have the same fingerprints. No matter who wins in 2008, they are "correct," simply by choosing which one to reveal.

Excellent work!

Sunday, November 25, 2007

My best way to get out of bed in the morning

Something I wrote in a chat log

12:17:34 AM: I was wondering once what would be the best possible way to wake up
12:17:57 AM: but which would force you to get up
12:17:58 AM: and I decided that if I was the richest person alive
12:18:11 AM: I would have a bed built so that when the alarm clock went off
12:18:34 AM: it would unhinge in the middle so the two halves would swing down and gently drop me
12:18:36 AM: into a hot tub
12:19:00 AM: which would be a great way to start the day, and there's no going back to sleep

Tuesday, November 13, 2007

Women's Rights are Human Rights

Maybe one day this will be reality, when women have the same definition of decency as men do.

The next step is naturally for social acceptability, then dare we entertain it, for it to be just as acceptable for men to wear bras and dresses. MLK had a dream too!

Starbucks' 87,000 options

I picked up a nutrition facts pamphlet at Starbucks that promises that with all the choices of creamer, syrup, spices, etc. "87,000" different beverages are possible.

Here's a computer science/reverse engineering problem. Find the number that is most likely to be the exact value of the number of options as Starbucks calculates it. Some things you might assume:

  1. It's likely to be within 500 of 87,000.
  2. It's factorization makes it look the most like the product of 2's, 3's or other small numbers reflecting many choices. For instance, it's unlikely to be 87011, which is prime. However, 87480 is a candidate since 87480 = 2 * 2 * 2 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 5. It's possible that there are 3 ingredients which you can have or not, explaining the 3 twos. Maybe there are 3 sizes, 2 types of toppings (and the option to have nothing), 2 kinds of creamer (or none), something else with 5 options, and finally 27 (3*3*3) different beverages. I don't know if this is how the Starbucks menu works and it doesn't matter: 87480 is definitely more likely than 87011.
I'd like to hear of good algorithms to solve this problem, and if anyone who reads this knows more about Starbucks, that's a fine way to answer too.

If we can't figure it out, let's not sweat it. I'm pretty sure that 87,000 is way too low anyway...