ASK THE ALGORITHM!

How do non-theorists view algorithms? If ask.com has its way they will associate algorithms with ask.com. Or they will associate ask.com with algorithms. There latest ad campaign seems to define algorithms to be search algorithms, which is even narrower than mine!. The company ask.com is bragging that their search engine uses an algorithm! Uh- we knew that. We also know that google and yahoo use algorithms! But apparently they don't use the algorithm.

I saw a billboard a few weeks ago which said

The Algorithm killed Jeeves.

Since I am a fan of of P.G. Wodehouse's fiction revolving around Jeeves and Bertie my curiosity was aroused. It turns out that this is ask.com's way of saying that they are changing their name from ask-jeeves to ask-the-algorithm (I'm not sure this is really their new name.) This is rather odd- you are supposed to kill the compeition, not your former selves.

This is only ask.com's second stupidest ad. The stupidest one is called the unabomber hates the algorithm What does this even mean? Nowadays most people have forgotten who the Unabomber is. But even if they know who he is, is the reasoning ``if a bad guy didn't like this product, then I should.'' ?
(Thanks to Paul Beame who send me this idea for a blog.)

The Man who loved Algorithms

The May 2007 issue of IEEE SPECTRUM has on its cover the sentence

The man who loved algorithms

I was thinking that it would be an article about Donald Knuth (See also Wikipedia entry) It was not- it was about Thomas Kailath(See also Wikipedia entry.) who won the IEEE spectrum medal of Honor for

exceptional developments of powerful algorithms in the fields of communications, computing, control and signal processing

I will defer to the IEEE and assume that he has indeed done excellent work. I had never heard of this person. Some of you may have since he does have some COMP SCI publications; however, I suspect most of you have not. If not, then do we have a narrow view of algorithms? My view is narrower than most and is summed up by a quote Michael Sipser said at a Workshop on Circuit Complexity about 20 years ago:

Algorithms are sanity checks on lower bounds.

$25,000 prize for ... Univ TM

1. Mike Pilat brought this to the attention of Lance Fortnow.
2. Lance Fortnow brought it the attention of Bill Gasarch.
3. Bill Gasarch brings this to your attention.

Mike's letter to Lance:

If you haven't already heard, my employer, Stephen Wolfram (and Wolfram Research) this week announced a $25,000 prize to prove or disprove that a particular 2-state, 3-color Turing Machine is universal (i.e., Turing-complete). If proven, it would be the simplest possible UTM. The details of the prize and the Turing Machine in question are all here. I thought you and your students might find this challenge interesting.

Is this interesting? Does offering $25,000 make it interesting? INTERESTING/NOT INTERESTING THINGS ABOUT TURING MACHINES:

INTERESTING: Turing Machines and seemingly unrelated models of computation are equivalent. NOT INTERESTING: Details of those equivalences. (They were clever and interesting at the time, but not now.)

INTERESTING: There is a Universal Turing Machine. NOT INTERESTING: Finding the smallest one.

INTERESTING: Turing Machines seem to capture all things that are computable. While usually called Church's thesis or The Church-Turing Thesis, Bob Soare thinks is should be Turing's thesis. See Springer LNIM, No. 4497, Computability in Europe, or just get it here.

INTERESTING: HALT is undecidable.

INTERESTING: The Busy Beaver Function (see also this) grows faster than any computable function, and hence is not computable. NOT INTERESTING: The actual values of this function. Especially since they would be tied to a rather particular type of Turing Machine (e.g., 1-tape, 2-symbol). Is the size of the smallest UTM or the values of the Busy Beaver function interesting to know for their own sake? How does this compare to finding actual Ramsey Numbers (see Dynamic Survey on Small Ramsey Numbers) or actual VDW numbers What are the criteria of interest?

1. Are these numbers interesting in their own right. For UTM NO, mostly because it is tied to a particular machine model. For Ramsey/VDW the numbers might be useful to inform conjectures. The few known values of VDW indicate that the VDW numbers may be far lower than the bounds given by the proofs.
2. Has nice math come out of the attempt? For UTM no, For Ramsey very little- R(4) uses Field Theory.
3. Has nice computer science come out of the attempt? For UTM/R/VDW the answer is yes- clever tricks and such. But (I think) nothing that can be used outside of these problems. If I'm wrong the commenters will politely correct me.
4. Why do people climb Mount Everest? Because its there! Finding these numbers may have the same mentality; however, its much safer.

Godel Prize: Natural Proofs. My 2 cents

As several readers mentioned on my last post, the Godel Prize has been announced. The award goes to the authors of a PAPER and the paper can be a conference paper, but it must have appeared in the last 14 years. They should have made it 16 years. The 2007 winners:

Alexander Razborov and Steven Rudich

for the paper

Natural Proofs, Journal of Computing and Systems Sciences, Vol 55, No 1, 1997, pages 24-35. Goto either of their websites for the paper.

This is an excellent paper about limits on proof techniques in circuits. Its been blogged about and been described in a wikipedia entry. Very recently Sivakumar wrote a very nice short description of the concept. Has it changed how we do research? The closest analog is the Baker-Gill-Solovay results on Oracles. The contrast:

1. Baker-Gill-Solovay showed that techniques that relativize do not suffice to resolve P vs NP. All proofs in recursion theory relativize. Hence we will need more than recursion theory techniques. (Some people disagree with this intepretation. If you are one of them, leave an intelligent comment.) Impact: (1) people got papers for constructing oracles to show that recursion theoretic techniques would not suffice to resolve certain problems, even problems nobody cared about. (2) people began looking more at combinatorial techniques such as circuits since those techniques tend to not relativize. One can argue if this is really true both mathematically and historically. It is possible that the move away from recursion theory to combinatorics was going to happen anyway, or already began. History is messy and hard to put into boxes.
2. Razborov and Rudich showed that all lower bounds for circuits (except monotone circuits, for which the terms don't really make sense) ``naturalize'' and that such techniques won't suffice to solve several problems in circuits, including P vs NP, under some reasonable assumptions. There has not been a rush to show certain results naturalize. There has not been a mass movement away from circuits towards something else. But there may be at some later time, and in any case the paper is crucial for telling us what we've been doing and what its limitations are.
3. Both results seemed to hint at independence results. Neither one has lead to any such results. Rudich told me once that they were 6 months away from an independence result. 10 years later he told me they are still 6 months away UPDATE IN 2014: STEVE RUDICH TELLS ME THAT HE NEVER SAID THIS. I BELIEVE HIM.
4. ``relativize'' was a natural notion that people already knew about at the time of the BGS paper. ``naturalize'' is a less natural notion that Razborov-Rudich discovered or invented for their paper. However it was a very important notion since it captured what many proofs had in common.

Money

When I was an Undergraduate (1976-1980) the question

Would you take grant money from the dept of defense?

was in the air. There were stories of people who thought they were working on medicine who were actually working on germ warfare. There were also stories about the people who worked on the Atom Bomb (knowing what they were working on) later regretting it.

I heard this kind of discussion less in grad school (1980-1985). The last time I ever heard it brought up at all was in 1989 when a grad student asked me if I take money from dept of defense. Since I've never been offered such money it was a moot point (I've never applied for such money, but not out of any moral principle.) I recently met up with that grad student (now a professor) and he is working on a germ warfare grant.

The question of who you take money from is asked in some circles- crypto comes to mind. But how about the general question- who would you take grant money from? There are several factors that people tend to lump together, but they are different:

1. Do they let you publish and post and talk about your research (e.g., NSA, Microsoft, might not)
2. Do you have a moral objection to who the person asking you? (e.g., the military)
3. Do you have a moral objection to the type of work being asked of you? (e.g., helping an advertising company sell more cigarettes to minors. When you question this they reply `if teenagers don't smoke, what will they do after sex?')
4. Is the work of interest to you?
5. Do you have to have a product in the end?
6. @
7. Will working on this put you in actual danger? (e.g., Tony Soprano wants you do use your knowledge of resource allocation to settle a gang war.)

There are many different possibilities. Here are two extreme cases:

1. Al Queda wants to give you a grant to work on something you like, and you can publish it, and it has no possible practical value. (You can replace Al Queda by whatever you think is a great evil.)
2. Greenpeace wants to know how to best lie to the public to force them to take action on Global Warming. You can't publish, post, or talk about it. The work is boring, and you find lying morally bad. But the cause is just! (You can replace Greenpeace and Global Warming with some other organization and cause that you agree with and think is very important.)

FCRC- deadline for late registration FRIDAY

The DEADLINE for registering for FCRC without paying a late fee is FRIDAY! However,

1. If you want to help the organizers in terms of allowing them to PLAN better, then register BEFORE the deadline.
2. If you want to help the organizes in terms of how much MONEY the conference makes then register AFTER the deadline.
3. To help them out in BOTH ways register ASAP after the deadline.

~

Believing an open problem has been closed

Frederic Green posted the following comment a while back:

Have you heard any buzz from your mathematical collegues on the alleged disproof of the Riemann Hypothesis.

Later comments indicated that the mathematician was not that good. When should you believe a math announcement? Which of the following would you believe? Would you bother downloading the paper?

1. Karp claims to have shown P = NP. P \ne NP.
2. Shelah claims to have shown P=NP. P\ne NP.
3. Widgerson claims to have shown P=BPP. P\ne BPP.
4. Bill Gates claims his group has shown P=NP and the binaries are available but not the source code.
5. The Free Software Foundation claims to have shown P=NP and of course the source code is available.
6. An undergraduate math major who is really sharp claims to have solved the the Collatz Conjecture) (also called the 3x+1 conjecture).

Whether to believe a claim is based on several variables.

1. G: How good is the person who claims to have solved it. Hard to measure. (number of STOC/FOCS papers :-) ) For someone new this might be even harder to access.
2. B: How believable is the result? We'd believe P\ne NP more than P=NP. But we may believe that if a proof was found now it would be that P=NP. I've heard that Riemann Hypothesis will probably be solved in the next 50 years.
3. H: How hard is the problem?
4. W: How good is the writeup? Is there one?
5. If the problem is outside of your area then you may have to take other people's word for some of G,B,H, or W. How good are the people telling you about the problem? This may lead to a recursive formula.

Green's Conjecture: There is a constant C such that

If G*B*W/H > C then the result is worth looking into.

If you claimed to prove Green's Conjecture then I could use Green's Conjecture to to see if your proof is worth downloading.

Coda to idiot-post

Coda to idiot.

1. The posting idiot was a test case for the newly-fixed mechanism to email posts to people (some people had been getting this blog via email instead of going to the web.) It did not work. Nobody knows why.
2. I had written:

   computers have gotten VDW(4,2) more complicated.

   One of the comments was:

   For the "Ramsey-theory idiots" out there, the technical translation of VDW(4,2) is "I don't know exactly how much more complicated computers have gotten, but its a while hell of a lot!" :-)

   The commenter is correct in clarifying what I meant; however, both the commentator and I are incorrect in the details. Inspired by the commenter, I looked up what is known about the VDW numbers. VDW(4,2) is known and is only 35. VDW(5,2) is known, and is only 178. I should have written VDW(5,5) which is unknown but quite likely quite large.
3. VDW(k,c) is the least number W such that no matter how you c-color the elements {1,2,...,W} there will be k numbers equally spaced (e.g., 3,7,11,15 is 4 numbers equally spaced) that are the same color. W(k,c) exists by van der Waerden's Theorem. See van der Waerden's Theorem-Wikipedia or van der Waerden's theorem-my posting in Luca's blog
4. I believe the only VDW numbers that are known are as follows: (see this paper) by Landman, Robertson, Culver from 2005.
   1. VDW(3,2)=9, (easy)
   2. VDW(3,3)=27, (Chvátal, 1970, math review entry, article not online.
   3. VDW(3,4)=76, (Brown, Some new van der Warden numbers (prelim report), Notices of the AMS, Vol 21, (1974), A-432. Article, review not online!
   4. VDW(4,2)=35, Chvátal ref above
   5. VDW(5,2)=178, Stevens and Shantarum, 1978 full article!