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 ${p}$ can be achieved using a combination of these stamps. That is, there exists ${p_0}$ such that for all integers ${p > p_0}$ there exist integers ${a,b \geq 0}$ such that

$\displaystyle p = 41a + 110b.$

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

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

$\displaystyle p_0 = v_1 v_2 - v_1 - v_2.$

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

• ${4360 = 50 \times 41 + 21 \times 110}$
• ${4361 = 101 \times 41 + 2 \times 110}$
• ${4362 = 42 \times 41 + 25 \times 110}$.

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 ${n}$ = 3 the only general formula known is a close lower bound on ${p_0}$. One can still play the game given particular values ${v_1,v_2,\dots,v_n}$ of the stamps. When ${n}$ itself is variable, however, the game is ostensibly too hard for a clerk, or anyone else: the problem of calculating ${p_0}$ is NP-hard.

This leaves the problem for fixed ${n}$. 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 ${n}$, 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 ${d}$ there are languages in the second level of the polynomial hierarchy that do not have circuits of size ${n^d}$. 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$\dots$

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

1. April 30, 2011 5:24 pm

“For n 2”?

• April 30, 2011 5:26 pm

(Hum, my previous post encountered a bug.)

“For n 2”?

• April 30, 2011 5:30 pm

(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”?

• April 30, 2011 7:24 pm

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…”

2. April 30, 2011 11:14 pm

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?

May 1, 2011 9:52 pm

A very nice piece!

4. May 2, 2011 7:50 am

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.

May 2, 2011 1:04 pm

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?

May 3, 2011 8:46 am

Anonymous,

They are different problems. When n is fixed it is in poly; when n varies it is NP-complete.

May 19, 2011 1:59 pm

But if for every fixed n it is in P, then the problem isn’t in P/poly?

May 2, 2011 2:01 pm

May 3, 2011 12:26 pm

I second this. Don’t leave us hanging!

May 3, 2011 8:12 am

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,

May 3, 2011 8:45 am

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.

May 3, 2011 11:28 am

Absolutly, thx. 😉

May 3, 2011 10:06 pm

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?