Easy, but not that easy

[Originally published on TypePad in August 2005; I’ve updated dead links, updated some terminology, and added footnotes describing more recent work.]

Lately I’ve been distracted by an open research problem left over from my PhD thesis. It’s a problem about lower bounds. When people design and analyze algorithms, they are proving upper bounds on the complexity of a problem. A lower bound, on the other hand, is a proof that the problem cannot be solved without using a certain amount of time (or some other resource), at least within a certain model of computation. Perhaps the most well-known lower bound is the statement that sorting an array of length n requires at least Ω(n log n) binary decisions—comparisons, for example.

So let me define a simple problem, which can be trivially solved in O(n²) steps using a simple pair of nested for-loops. The open question is whether there is a faster algorithm.

AlignedSumLess:
Input: arrays A[0..n], B[0..n], and C[0..2n] of real numbers.
Question: Is A[i] + B[j] < C[i+j] for any indices i and j?1

I repeat: Nobody knows whether this problem can be solved in subquadratic time.2 The best lower bound in any general model of computation (algebraic computation trees, or equivalently, the so-called Real RAM) is Ω(n log n), and this derives essentially from the same information-theoretic argument as the sorting lower bound.

(What do I mean by a “general model of computation”? A technical definition is a bit difficult, but essentially I mean a definition of “algorithm” that doesn’t seem tailored to the problem, or even worse, to the algorithms that we already know for solving the problem. What I most certainly do not mean is “Turing machine”—we want to allow primitive operations that Turing machines can’t do quickly (like random access memory) or at all (like exact real arithmetic). Here there be dragons, or at least, cans of worms.)

It’s not hard to prove an Ω(n²) lower bound in a model where the algorithm is only allowed to branch using questions of the form “Compare A[i]+B[j] to C[k]”. The proof uses an adversary argument. Imagine a game of “(n+1)² questions” between two players, one (the algorithm) asking questions, the other (the input) answering those questions. The algorithm’s goal is to solve the problem as quickly as possible; the input player’s goal is to drag out the game as long as possible. The algorithm wins if he can produce the correct answer after asking fewer than (n+1)² questions; otherwise, the input player wins.

Now imagine that the input player actually an all-powerful malicious adversary. Rather than thinking of a specific input in advance and answering questions accordingly, the adversary chooses answers on the fly to make the algorithm’s life difficult, but always in a way that is consistent with some input. In other words, the adversary can cheat as much as he likes, as long as he doesn’t get caught. Moreover, the adversary knows everything about the algorithm—the code is written on the wall, so to speak—but the algorithm knows only what the adversary tells it.

So here’s our adversary strategy. During the game, we pretend that A[k]=B[k]=6k and C[k]=6k-5 for all k, and we answer every question honestly. With this input, the algorithm’s correct answer is No. Now suppose the algorithm declares a solution without comparing A[i]+B[j] to C[i+j]. We can modify the input, setting A[i] = 6i-2, B[j] = 6j-2, and C[i+j] = 6i+6j-3 but leaving everything else unchanged, and then triumphantly (and correctly) declare “Aha! You’re wrong!” All of our earlier answers are consistent with this newly modified input, so as far as the algorithm knows, that was the input all along! The only way that the algorithm can avoid being fooled is to compare A[i]+B[j] to C[i+j], for all (n+1)² pairs of indices i and j. The adversary always wins!

So in the worst case, the algorithm must ask at least (n+1)² questions to obtain the correct answer, QED.

In my thesis, I extended this adversary argument to allow a larger class of questions, like “Is the expression α A[i] + β B[j] + γ C[k] + δ positive, negative, or zero?” where α,β,γ,δ are arbitrary real numbers. Algorithms that onlly ask questions of this form are called 3-linear decision trees, because the questions ask about the sign of linear expressions involving three of the input values.

Now let’s consider the following related problem, called min-convolution, min-sum convolution, infimal convolution, inf-convolution, or tropical convolution, depending on who you ask. This problem has lots of applications.

(Min,+)-convolution:3
Input: arrays A[0..n] and B[0..n] of real numbers.
Question: For each integer k between 0 and 2n, compute min_i (A[i] + B[k-i]).

Like the earlier problem, we can easily solve this one in O(n²) time with a pair of nested for-loops, and nobody knows whether that is the fastest algorithm.4 Unlike the earlier problem, however, we don’t have a quadratic lower bound for (min,+)-convolution in any model of computation. Our ignorance is complete!

If we had a fast algorithm for this problem, we could easily transform it into a fast algorithm for AlignedSumLess, just by comparing the (min,+)-convolution of A and B to the input array C. Conversely, if we could prove a Ω(n²) lower bound on the complexity of AlignedSumLess, that would immediately imply a Ω(n²) lower bound on the complexity of (min,+)-convolution.

But we have a Ω(n²) lower bound on the complexity of AlignedSumLess, at least in a restricted model of computation. Why aren’t we done? Because the model of computation is too weak! Intuitively, we can’t solve (min,+)-convolution at all without allowing comparisons of the form A[i]+B[j] <? A[i’]+B[j’], and our model of computation doesn’t allow that: too many input variables are involved.

What we need is a Ω(n²) lower bound for AlignedSumLess in the 4-linear decision tree model. I don’t have a clue how to do this. The earlier adversary argument completely breaks down once we allow these four-variable questions.5 Nir Ailon and Bernard Chazelle recently made some progress on proving that harder variants of this problem are, in fact, harder, but their techniques also break down for problems that are this simple.

It’s hard to prove that easy problems aren’t trivial!

Computational geometers might wonder whether there is any connection between these apparently-quadratic problems and the problem 3SUM: Giiven a sett of numbers, do any three sum to zero? The answer is yes, but not the way you might like. Both 3SUM and AlignedSumLess are provably harder than the following totally artificial problem (at least in restrictions of the algebraic decision tree model):

Polyhedral 3SUM:6
Input: arrays A[0..n], B[0..n], and C[0..2n] of real numbers, such that A[i] + B[j] ≤ C[i+j] for all indices i and j.
Question: Is A[i] + B[j] = C[i+j] for any indices i and j?

Don’t ask how we know those input inequalities are satisfied. Let’s just say the knowledge comes down from Mt. Sinai engraved on stone tablets. Can this problem be solved in subquadratic time? Not in the 3-linear decision tree model, but beyond that, nobody knows.

Perhaps the “right” way to think about this problem is geometrically. We are given a point x inside a particularly nice closed (4n+3)-dimensional polyhedron defined by (n+1)² inequalities. Does the point lie on the boundary of the polyhedron? Sure, we can just check each inequality one at a time, each in constant time, but can we do better? The earlier adversary argument implies that none of the inequalities is redundant—the polyhedron has exactly (n+1)² facets. But maybe there’s a hyperplane that separates the facets nicely, or something. Or maybe not. We just don’t know!7