Congrats Ravi Kannan

One aspect of Kannan’s great work

Ravi Kannan has just been awarded the 2011 Knuth Prize.

Today I wish to congratulate Ravi on being awarded this great prize. It is a terrific choice—he very much deserves the honor.

I once posted on Ravi and said:

Ravi Kannan is one the top researchers in the known world on computational complexity aspects of linear algebra. His Ph.D. thesis is on the complexity of computing the Smith Normal Form of a matrix; one of his best results is on computing the approximate volume of a convex body in high dimensions; and his most “magical” result is on the power of random sampling for linear algebraic computations. He was awarded the Fulkerson Prize with Martin Dyer and Alan Frieze for their wonderful work on the volume problem.

I cannot add much to this: Ravi has worked on and solved many important problems. He is also one of the nicest people in the world. Perhaps the prize should only be decided by accomplishments, but he still is one of the nicest.

Sometimes we forget that these prizes are decided by committees and I want to list them and thank them for their time and effort. The whole theory community owes them a thanks for their work and wisdom:

• Joan Feigenbaum
• David Johnson
• Ming-Yang Kao
• Nancy Lynch
• Ronitt Rubinfeld
• Eli Upfal

A special thanks goes to Nancy who chaired the committee.

Royal Wedding and Frobenius Problem

Yesterday was the Royal Wedding of Prince William and Catherine Middleton. The Royal Mail released commemorative stamps for the occasion (the image is taken and cropped from the latter link):

These stamps come in two denominations: the current UK first-class rate of 41 pence, and a stamp for 110 pence. This section is due to Ken, who understands the British currency system—among many other things—no doubt since he obtained his graduate degree at Oxford. As in Oxford, England.

Since 41 is prime, these numbers are relatively prime, and so every sufficiently large postage amount can be achieved using a combination of these stamps. That is, there exists such that for all integers there exist integers such that

The Frobenius problem, which is more often stated in terms of coins than stamps, is: What is the smallest that works? Or alternatively, what is the largest integer amount that cannot be achieved by combining the available denominations of stamps? It is named after Ferdinand Frobenius.

The problem generalizes to any number of different stamps whose values have no common divisor. A simple closed-form formula is known only for = 2: if the values of the two stamps are and , then

For William and Kate’s stamps, that means 110*41 – 151 = 4,359, so £43.59 (that is 43 pounds and 59 pence) is the largest amount that requires some other stamps. A handy fact for a postal clerk to know, at least to win beer bets in a pub. Notice that

• 
• 
• .

The game is pleasant to play with their stamps because multiples of 11 are easy to recognize by the difference of the sums of the even and odd digits itself being a multiple of 11. Thus to test 4,363 you can subtract off 3*41 = 123 to make the final digit 0, then subtract 410 until getting a multiple of 11. That 4,359 is impossible can be proved the same way. Once you’ve done 4,359 and the next 37 numbers, every number after that differs by a multiple of 41, so you know how to create the desired postage.

When you have three or more kinds of stamps the game becomes harder, especially to prove that certain numbers are impossible. For = 3 the only general formula known is a close lower bound on . One can still play the game given particular values of the stamps. When itself is variable, however, the game is ostensibly too hard for a clerk, or anyone else: the problem of calculating is NP-hard.

This leaves the problem for fixed . People had tried to create algorithms for it out of elementary number-theoretic thinking, but it took his consciousness-raising previous work with László Lovász and Herbert Scarf on lattices and polyhedra for Ravi Kannan to solve it. He proved:

Theorem: For every fixed number of stamps , there is a polynomial time algorithm to solve the Frobenius problem.

Ravi did this by using some beautiful results from the geometry of numbers: some old, some new, and some borrowed. I think he skipped using anything blue. I am not sure what that would mean for mathematics, though the use of an IBM “Big Blue” computer would qualify. The tradition for brides is to make sure they have old, new, borrowed, and blue.

Open Problems

Perhaps the main open problem today is to collect some fun Ravi stories. I have given several in earlier posts. Do some of you have some additional ones to add? If prompted I may relay the story of the German Chocolate Cake.

Among my close encounters with Ravi’s work is his theorem that for every there are languages in the second level of the polynomial hierarchy that do not have circuits of size . We have blogged about the open question of extending its application here among other places. To quote the romantic song from this romantic movie, “It’s still the same old story”

[fixed title and pound sign and made numbers look better in main text]