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]
“For n 2”?
(Hum, my previous post encountered a bug.)
“For n 2”?
(I see. Third time’s a charm.)
“For n < T the only general formula known…”
What is T? Is it supposed to be “n > 2”?
I figured you’d wish the other tries taken out—the trouble is that in some cases a less-than sign is parsed as if it began some funky HTML tag. Can’t tell where see a “T”, however…the post has what I’d written, “For n = 3…”
The Frobenius algorithm sounds like a very cool result. I was trying to think of variant questions; here’s one that could conceivably be interesting.
Fix a number k of denominations.
Input: values d[1], …, d[k] of the denominations,
AND nonnegative integers m[1], … , m[k].
(Interpretation: you have m[i] copies of the i-th denomination.)
Output: The least amount of change that you could make with these denominations, but are prevented from making due to the limited available copies.
Solvable in polynomial time for fixed k?
A very nice piece!
I don’t have a fun story about Ravi, but nevertheless something interesting IMO. I worked with Ravi and Navin Goyal last summer: I was quite amazed that we could essentially walk into his office any time and that he was willing to drop his current work and continue our discussion. It is an inspiring memory.
Hearty congrats, Ravi.
Very nice post!
I have a dumb question: Ravi’s result shows that the Frobenius problem is in P/poly, and Ramirez-Alfonsin proved that it is NP-hard (and as we can give a certificate, is is NP-complete). So this implies that NP is inside P/poly?
Anonymous,
They are different problems. When n is fixed it is in poly; when n varies it is NP-complete.
But if for every fixed n it is in P, then the problem isn’t in P/poly?
Let’s please hear that story about the German Chocolate Cake, please!
I second this. Don’t leave us hanging!
Hello,
»For every fixed number of stamps , there is a polynomial time algorithm to solve the Frobenius problem.
I don’t get this one: if the number of stamps (called n) is fixed, then what does it mean that a polynomial time algorithm exists? Or it’s polynomial as a function of some other n such as the combined size of v1, v2, … vn?
Thx,
Jiav,
The number of stamps is fixed, but their values can be large. For example, when n=3 the stamp values could be 65352635, 7188774821, 872487811. The size of the numbers is what the algorithm is polynomial in. I hope that helps.
Absolutly, thx. 😉
Judging from the abstract, it looks like he actually constructed an algorithm for a fixed n. This is more significant than just proving existence. Just curious, has anyone implemented the algorithm yet in code?
Just looked at the date on that paper. It’s not as recent as I first thought. 🙂
Jakun:
Matthias Beck, a mathematician at San Francisco State University gave a talk five or six years ago on Frobenius problem. If I recall correctly, he mentioned that he (or some colleague) had implemented Ravi Kannan’s algorithm because they needed to solve some specific instances of the Frobenius problem. I think he mentioned that the algorithm was not fast enough to give a solution to their instance.