dana blogs math: The Talk That Wasn’t

Manuel Blum, 1995 Turing Award laureate and citizen of the Milky Way Galaxy. (Photo courtesy of Marlene Knoche.)

(Originally posted 26 September.) Today I had the real privilege of hearing Manuel Blum‘s talk at the Heidelberg Laureate Forum. It was about…

“Wait a minute!” I hear you saying. “Manuel Blum didn’t give a talk at the forum!”

Well yes, that’s right, he didn’t. But at least he told me about the talk he would have given if he had chosen to give a talk. It was about…

“Wait a minute!” says Eric Chung of Microsoft’s eXtreme Computing Group. “Let me tell you my story about Manuel Blum. I was taking a course on algorithms from him at UC Berkeley. For some reason I had to miss class for a week, and I missed a test. So he told me to come to his office, and he would give a test to me orally.

“I studied like crazy, and went to his office with my head full of the questions that he might ask. He told me to come in, and then he asked me, ‘You’re working in hardware, right?’ I told him yes, and he said, ‘Why don’t we go to your lab and take a look at what you’re doing?’

“So I took him to my lab and I showed him this and that, and he asked me lots of questions about my work. I could see he was really interested. This went on for a while, and finally I asked him about the test.

“‘The test?’ he said. ‘You got an A.'”

Even though I only met Manuel Blum this week, I feel as if this story says something very important about him as a scientist, a teacher, and a human. Here’s a person with a genuine curiosity about everything. It doesn’t matter whether you are a student or a world-famous scholar, if you have something interesting to say — or even better, an interesting problem to think about — he wants to hear you. Compared to understanding how the world works, little things like tests are unimportant.

Which reminds me, I was going to tell you about the talk he would have given here in Heidelberg. It was about…

You can take mathematicians out to the country, but you can't stop them from thinking about math. Manuel Blum (left) and Eric Blais (right) concentrate intensely.

No, first, Manuel himself wants to tell you about the two problems he heard about on the boat ride yesterday, both from young researchers. Actually it was three problems, because I remind him that he and his great-grand-student Eric Blais were talking about a problem when I sat at their table last night. Unfortunately, Eric didn’t want me to divulge the problem in my blog because he wants to work on it some more first. But I can tell you the other two.

First, Johannes Ruf told Blum about a problem that runs somewhat like this. (Blum says that this is his modification of Ruf’s problem, but it’s still recognizably the same genre.) It’s a version of Russian roulette played by 100 people, who are numbered from 1 to 100. There are 100 doors, and each person gets to pick 99 of them. Behind each door is a number. If he happens to pick a door with his number behind it, then he is safe (for the moment) and the next person gets to choose 99 doors.

I should mention that the 100 people do not get to see what is behind the doors that the other people choose. They cannot have any communication during the game, although they can strategize before the game begins.

Now what happens if player 2, or any player, does not choose the door with his number behind it? Well, then it’s very bad news. Not only does that player get killed, but so does every other player. Ouch! This is a really harsh version of Russian roulette.

Now the question is: Since the players are allowed to talk about strategy beforehand, what is their best strategy? Let’s look at a couple possibilities.

First, they could agree that all of the first 99 players will open the first 99 doors. If all of them survive, it means that the first 99 doors had numbers 1 through 99 behind them. Knowing this, the 100th player can simply pick door 100, and he will know that it has the number 100 behind it. Everyone will live.

Unfortunately, this is a really bad strategy, because if door 100 doesn’t have 100 behind it, then everyone gets killed. Probability of survival: 1/100.

A much better strategy, it turns out, is for everybody to pick at random. Then the probability that everybody survives is (99/100) to the 100th power, which is about 1/e (or better than 1/3).

Ruf’s question is simple. The random strategy looks pretty good. Is it in fact the best strategy?

What a cool problem! It takes a known fact (that 1 – 1/n raised to the n-th power is about 1/e) and puts a whole new spin on it. Instead of calculus, we are now in the realm of games and strategy.

The third problem that Blum heard about on the boat ride was from Gergely Ambrus.This one is an old chestnut: You’re supposed to find the volume of a sphere with a hole drilled out of it, and you’re only told the length of the hole. It doesn’t seem as if this could be enough information to compute the volume, but in fact it is. Blum had seen the problem before and knew the answer, but he said he has never seen a really satisfactory explanation for why the sphere’s radius, r, doesn’t matter. Ambrus told him, “Oh! I can explain that!” and proceeded to show Blum how to set up the volume as an integral with r in the numerator and r in the denominator. The r’s cancel out, and so the volume is independent of r. Then you can find it simply by setting r = h/2 (half the length of the hole), in which case the hole has to have width 0 and volume 0 and the volume is simply that of the sphere. “You don’t even have to compute the integral!” Blum told me with glee.

Anyway, now let me tell you about the lecture that Blum would have given at this meeting. It was about…

No, wait a minute. He wants to tell you about the problem his student, Mehdi Samadi, is working on. Samadi wants to write a better version of Google (better at least for scientists).

Here’s the problem, as Blum explains it. Suppose you input a factual statement into Google, such as “the cholesterol in shrimp is more healthy than in meat.” Google will give you a bunch of results, but you don’t know which ones to trust. Samadi’s program will go through the Google results and, first of all, shade a result green if it supports your factual statement, red if it is against your statement, and white if it’s neutral. Then it will shade it darker if the statement comes from a reliable source, or lighter if not. Thus, for instance, if the frozen food association says that shrimp is better for you, it might get a lighter shade. If a study from Rockefeller University says it’s better, that would get a darker shade. If, on the other hand, the Rockefeller study had only 20 people subjects, the shade might get lighter again.

I keep saying “might” just because Blum might have been simplifying and my notes might not be accurate, but this is an actual example that Samadi has done. Not only that, his program is impressive enough that he has gotten a large amount of funding to set up a company.

But that’s not really the cool part. The cool thing that Blum is itching to tell you is that on the boat ride yesterday he met two computer science students, Johannes Hoffart and Mohamed Yahya at the Max Planck Institute, who are working on natural language processing — which is just the part that is missing from his student’s software.

Out of such boat trips are great technological innovations born.

Well! That was fascinating. But now let me tell you about the lecture that Blum would have given at the forum. It was about…

Darn it! There’s the bell for the next talk! Do you mean to say our interview is over so quickly? Time sure flies when you’re having fun!

This blog post originates from the official blog of the 1st Heidelberg Laureate Forum (HLF) which takes place in Heidelberg, Germany, September 22 – 27, 2013. 40 Abel, Fields, and Turing Laureates will gather to meet a select group of 200 young researchers.

Dana Mackenzie is a member of the HLF blog team. Please find all his postings on the HLF blog.