Beating Bellman for The Knapsack Problem

Daniel Lokshtanov is a research fellow in algorithms whose Ph.D. was on parameterized algorithms and complexity. When I looked at his home page I saw his email address is written in the form:

name [at] somewhere [dot] rest of the address

Of course the point is to “fool” robotic agents, and make it harder for them to collect email addresses for spamming. I have always wondered if this method really works, but at first glance it looked like he had gone one step better. His homepage was even trickier: it says his email is his office location and his phone number is his email. I thought: what a clever trick. But, Subruk pointed out, if I just maximized my browser window all would line up—he was right. Oh well.

Today I will talk about a paper in the upcoming STOC conference on, among other things, one of my favorite problems: the Knapsack problem. The paper, authored by Daniel and Jesper Nederlof, uses a “new” method, and the method yields, in the their hands, some quite striking results.

As with many new methods, the method is not completely new. I sometimes wonder why it is so hard to figure out who invented something. I think figuring out the inventor of a method rather than the inventor of a theorem is even harder. A theorem is a precise statement and acts like a point; a method is a general idea and acts more like a cloud. I can think of many examples of methods whose correct history would be hard, if not impossible, to unravel.

Some of the issues blocking the definitive statement of who invented a method are:

• Sometimes methods are independently discovered in essentially the same form. Until researchers become aware of each others work, it is often hard to decide who did what when. Even a result published in a well known conference or journal can be innocently missed. The amount of material published these days makes searching harder than ever.
• Sometimes methods are discovered in slightly different forms. Even if researchers are aware of each others work, they still may not realize their respective methods are really the same.
• Sometimes methods are discovered in different parts of science. In this case it is quite easy for researchers to have no idea the method is already known. A perfect example of this is probably the various “discoveries” of the quadratic algorithm for the edit distance problem.

The method used by Daniel and Jesper was used previously by Yiannis Koutis—at least both used a very similar idea. So did Yiannis invent the method? I do not know, nor will I try to do a definitive historical study, but will try to point out the beautiful work that Yiannis also did.

Before we worry about who invented the method, let me explain what the method is.

The Method

Suppose you wish to calculate some value . The CEM method has three steps:

1. Define a polynomial so the coefficient of a given monomial of is equal to .
2. Construct an arithmetic circuit that computes the value of at any point efficiently.
3. Use a fast algorithm to determine the coefficient of the given monomial.

The name, CEM, stands for Coefficient Extraction Method—please suggest a better name, but for today I will use this name.

There are several remarks I will make about CEM. The first two steps, defining the polynomial and the arithmetic circuit, are quite creative. Each application requires that you figure out how to make your value appear in a known monomial of an efficiently computable polynomial. The last step is a general lemma—so this step is essentially automatic.

The CEM method has more flexibility than the version I have given. The ring the polynomial is defined over can be selected in a clever manner too. For example, in some applications the ring is the integers, in some the complex numbers, in others it is a more general commutative ring. The latter happens in the work of Yiannis. This is an additional degree of freedom, and can be exploited to make CEM work to solve your problem.

Another source of greater flexibility is the monomial. In many application the monomial is exactly known. In other applications the monomial is only partially known: for example, the key value may be the coefficient on any monomial of the form

where all the exponents must be odd. Clearly, the CEM is a powerful family of tools—this is the reason such pretty results have been obtained with the method.

Constant Term Method

As I have already stated, it is often the case with a “new” method, there is an older method quite similar in spirit to it. The constant term method (CTM) is used in combinatorics to enumerate many interesting objects and is very close to CEM. The CTM method uses a Laurent polynomial so that the constant term of has the same value as whatever you wish to count. Since is a Laurent polynomial it can have negative as well as non-negative powers of . Thus,

is a perfectly fine Laurent polynomial. Note, the constant term of is not simply : the value of the function may not be defined at .

A famous example, of this is the Dyson Conjecture: the constant term of

is equal to

The conjecture, now a theorem, was made by Freeman Dyson in 1962—it arose in a problem in particle physics.

There is one fundamental difference between CEM and CTM, besides the simple difference: CEM allows any coefficient and CTM always means the constant term. In combinatorics almost always one wants an expression for the term; in complexity theory one is usually happy with an algorithm for computing the term. We do want efficient algorithms, but do not need or expect the term will have a simple closed form expression, we might even allow small errors. In combinatorics the closed form solution often gives additional insights: for instance, using a closed form may allow a simple argument about the parity of the coefficient.

Applications of CEM

I would like to give two basic applications of CEM. As usual please see Daniel and Jesper’s paper from STOC and Yiannis’ paper from ICALP for details and exact statements.

The STOC Paper

Consider the subset sum problem: Given a set of natural numbers is there a subset of so,

where is the target. Let be the polynomial,

The key is that the coefficient on is non-zero if and only if the subset sum problem has a solution. This follows since,

where is the number of ways to multiply the terms

together and yield .

It is easy to see that this polynomial has an efficient arithmetic circuit, and thus CEM can be applied. Pretty neat.

The ICALP Paper

The second application uses a generalization (GCEM) of CEM: the detection of any multi-linear term in a polynomial whose coefficient is odd. Consider the -simple path detection problem: Given a graph is there a -simple path in the graph. There is a very clever reduction of this problem to the generalization of CEM that yields a random algorithm whose dominant cost is order . The exact running time is bit more complex, and one of the great things about the algorithm is it uses only polynomial space.

A Lemma

I will present one sample lemma—see the papers for details on how to solve CEM and GCEM.

Given a polynomial the key parameters are where each term of is

and is the maximum of ; and the size and depth of the circuit that computes the polynomial. Then, CEM can be solved in time roughly —leaving out lots of logarithmic and other low order terms. Also the space of the algorithm is quite small, the dominant term is .

While I will not state the lemma Yiannis uses in any detail, there is one aspect of his lemma I really like. As I stated before the methods can use different rings—they need not be restricted to integers or reals or even complex numbers. In Yiannis’ work a trick he uses is to work over a ring that has nilpotent elements: recall is nilpotent if some power of is . See his well written paper for the full details.

Open Problems

The main open problem is can we use CEM to solve some other open problems? I am trying to use the method to solve some old problems, but have not had any success, yet. The method seems quite powerful, and I hope you can use it to get new theorems. Good hunting.