Skip to content

Leprechauns Are Tricky

March 17, 2012


Happy St. Patrick’s day

Neil L. is a Leprechaun, as you may know.

Today Ken and I want to relay what happened late last night, right before St. Patrick’s day.

The last few years he has visited me, and I expected him again this year. I stayed up late and sure enough he suddenly appeared in a cloud of green smoke that emanates from his pipe. While the smoke is green it has a pleasant smell, one that I cannot place—it is so hard for me to describe smells.

Neil said, “Ha, you did not catch me this year, so no three wishes for you.” Last year I had caught him and was granted three wishes. At that time he explained they could not be any wishes, but there were rules. I recall his saying:


Over the years there have been some abuses of wishes, so there are rules among Leprechauns. The wishes may request only information—they cannot not ask for money, or some strange power, or more wishes…

The questions I had asked were an attempt to get a proof out of him about {\mathsf{P}=\mathsf{NP}}. You can see for yourself that he beat me—each question was answered in a way that was useless.

I was glad that I did not have any wishes this year. I said, “Neil, I may call you Neil?” He nodded. “I am glad I have no wishes this year, Neil—you are too clever for me.” At this he smiled and puffed away on his pipe. This time I thought I would just lie low.

Neil’s Near-Giveaway

Neil said, “Yes—no wishes for you this year, I laugh whenever I think of last year. But you were a good sport.” I thanked him and was about to speak when he interrupted me and said:

“What is with all this stuff on quantum? We leprechauns follow your blog, but I cannot see why you care so much about quantum computers. Why we have known for years that they are clearly {\dots}

He stopped mid-word and with a catch of breath put his hand up to his mouth. Then he sighed, “I see your game this year—I almost gave away the secret. I would have been in great trouble with the boss—that was close.”

I asked who was his boss, but that only got a wave of his hand—it was clear that I was not to hear any more about that. Instead Neil said “I enjoy these visits, I wish I could come more often, but very busy year.” I asked what did he do during the year? He started to say the usual leprechaun things, making shoes, playing tricks, and mostly enjoying his green smoke from his pipe—but then his hands went up again: “I must tell you—I was trapped!”

Trapping, Hashing, and Obfuscating

Neil had told me before that people were always trying to trap leprechauns, and he had to be careful.

But he wasn’t careful enough, and another computer science theorist—whom I will only call Dr. T—caught him fair and square. As the setting sun faded the rainbow he had been too slow to whisk back before tripping over his hat, Neil realized a flaw in the new leprechaun law. Dr. T could not ask for his pot of gold directly, but could ask for information on where to find it—and since leprechauns cannot lie, he had to tell Dr. T where.

Neil tried the historical leprechaun trick. Since it was too late before dark to dig up the gold, he offered to lead Dr. T to the tree where it was buried, and tie a yellow ribbon around that tree to mark the spot. But Dr. T would have none of that:

“I know your tricks. When I come back in the morning you’ll have tied yellow ribbons around every tree, and I’ll have no bits of information about the gold. Hello—it’s the 21st Century—so I demand the authenticated GPS co-ordinates of your gold!”

“Authenticated?” “Yes—by a secure and precise geohash function, encoded as a URL via the geohash.org web service.” Neil thought quick and asked, “Using the algorithm on the Geohashing Wiki?” “That’s right—follow the directions as-given on the wiki named for the service, nothing else—no tricks.”

Neil inserted a tone of reproach that people in my field were looking to Wiki-this-and-that as an icon of standardness, rather than the Encyclopedia Britannica from his home isles. “Dr. T got just deserts, and probably after The Algorithm did its magic, got just deserts.”

Complexity

But then Neil re-lit his pipe and drew his face forward to me earnestly. “You really should do more with hashing. Forget the quantum—didn’t you once work on hiding code with hashing? Or something like that? Hashing is where the future is—look how it saved my gold.” I told him that yes hashing was coming back into fashion in theory, and we would do some blog posts on it.

Then I asked him which were his favorite recent results in complexity theory. He said that he especially liked the improvement of the exponent on matrix product by Virginia Vassilevska Williams after Andrew Stothers—see here for our discussion about it.

I said that I was quite surprised to hear this. The improvement was so small. But he said, “No, I really like the result—we leprechauns are small people, so we appreciate small improvements.” I casually said that we all had our conjectures about the Strassen constant, {\omega}, but it was not even clear what the first number was after the decimal point. I added, “of course no one has any idea what it could be.” Neil smiled and said,

“Oh that is not true, the number after the dot is a zero, for sure.”

He then looked a bit annoyed that he had said this, and in a puff of green smoke he was gone.

I was excited—so Strassen was almost two, that was a cool fact. But it quickly hit me that I had been tricked again. Neil had fooled me again. Do you see why?

Open Problems

If Neil gave no information about {\omega}, how was he counting?

Have a safe and fun St. Patrick’s day.

14 Comments leave one →
  1. March 17, 2012 7:35 pm

    Neil L., quantum is what makes gold atoms and rainbows possible.

  2. Jim Blair permalink
    March 18, 2012 7:10 am

    “If Neil gave no information about’w’, how was he counting?”

    Binary decimals?, where:

    0.10 = 0.50

    0.01 = 0.25

    0.11 = 0.75

  3. March 19, 2012 1:39 pm

    He didn’t specifically say the first number after the dot, did he?

  4. Sniffnoy permalink
    March 22, 2012 4:00 pm

    Base 2 is sufficient to give no information; we already know that omega is less than 2.5.

    • March 23, 2012 5:31 pm

      How about if leprechauns used the Golden Base—would Neil be giving information then?

      • Jim Blair permalink
        March 24, 2012 11:46 pm

        Guessing Yes.

        Square root of five equals 2.236 equals 10.1 Golden Base.

        If there was a zero after the dot, he would have revealed omega was less than 2.236 which is better than the known 2.37.

      • Jim Blair permalink
        March 25, 2012 2:10 pm

        10.0110100111001(Phi) = 198Phi-318 = 2.3707297724791942(approx)

        To be more precise.

      • Jim Blair permalink
        March 25, 2012 11:00 pm

        On the other hand:

        1.1101111110111(Phi) = 198Phi-318 = 2.3707297724791942(approx)

        We can’t tell?

  5. March 24, 2012 3:34 am

    hindu tricks … the number after the dot was a zero!!

  6. March 26, 2012 7:40 pm

    ……..02.xxxx

Trackbacks

  1. Happy St. Patrick’s Day—Again and Again and Again and Again | Gödel's Lost Letter and P=NP
  2. More on the Diagonal | Gödel's Lost Letter and P=NP

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s