### Joint computational complexity, and the "buy-one-get-one-free conjecture"

Below is a simple-to-state open question, stemming from this paper of mine from CCC'09. First, I'll state the question; then I'll give some background, explaining how it's an instance of a more general and significant problem.

**The question**

Let's consider the standard two-party model of communication complexity. Given inputs *x* and *y *to Alice and Bob respectively, suppose there are 3 functions the two parties are interested in evaluating on these inputs---let's call them *F(x, y), G(x, y), H(x, y).*

**Question: **is there a collection of total functions *F*, *G*, *H*, and a positive value *T*, such that:

**(i) **any one of *F*,* G*,* H* requires at least *T* bits of communication to compute;

**(ii)** any **two** of *F*,* G*,* H* can be computed in *(1.01 T)* bits of communication, on a **common input** *(x, y)*;

**(iii)** but, computing all three of *F*, *G*, *H* on a common input requires at least *(1.99 T)* bits of communication.

I believe such a collection exists. We can call this the **'buy-one-get-one-free conjecture'**: Think of *T* as the individual 'price' of the 'items' *F*, *G*, *H*; we want to arrange a special 'deal' where the second item is essentially free, but one has to pay full-price for the third item.

Now if you think about it, what we're looking for is pretty strange. The function *F* should be efficiently computable in at least two 'essentially different' ways---one of which also gives us the value of *G*, and one of which gives *H*---yet there should be no efficient scheme to compute *F* that gives us *G* and *H* simultaneously. (This property seems easier to contrive when the inputs *x, y* are assumed to have a special, correlated form; I rule this out by insisting that *F, G, H* be *total* functions.)

The question makes equal sense when posed for other models of computation. In my paper, I proved the corresponding conjecture in the decision tree model of computation, as a special case of a more general result--see below. Communication complexity could be a reasonable model to attack next.

**Please note: **While this conjecture may require lower-bounds expertise to resolve, I believe that anyone with a creative spark could make an important contribution, by coming up with a good set of *candidate functions* *F, G, H*. Please feel encouraged to share any ideas you might have.

**Background on the question**

Let *cc(F)* denote the (deterministic) communication complexity of computing *F(x, y)*. Next, let *cc(F, G)* denote the communication complexity of computing *F(x, y) *and *G(x, y)*---on the *same* input-pair *(x, y)*. We define *cc(F, H)*,* cc(G, H)*, and *cc(F, G, H)* similarly.

Together, we think of these various quantities as summarizing the 'joint complexity' of the collection *F*, *G*, *H*. Of course, this notion can be extended to collections of *k > 3* functions; the joint complexity is summarized by giving the communication complexity of all *2^k* subsets of the collection. Let's let *JC* denote the function that takes as input a *k*-bit vector, and returns the complexity of computing the corresponding subcollection. So, in our 3-function example, we have

*JC(1, 1, 0) = cc(F, G)* and *JC(0, 0, 1) = cc(H)*.

The question we want to ask is: what kinds of behavior are *possible* with the joint complexity, if we allow the functions *F*, *G*, *H*, etc. to be chosen arbitrarily? In other words, what different types of 'efficiencies' can arise in a collection of computational tasks (in the communication model)?

A little thought reveals some obvious constraints:

**1.** the joint complexity function *JC* must always be nonnegative and integral-valued, with *JC(**0**) = 0*.

**2. monotonicity: **Enlarging the subset of the functions to be computed cannot decrease the complexity. For example, we always have *cc(F, G) >= cc(F)*, which translates to J*C(1, 1, 0) >= JC(1, 0, 0)*.

**3. subadditivity:** Taking the union of two subsets of functions to be computed cannot increase the complexity beyond the sum of the individual complexities of the subsets. For example, *cc(F, G, H) <= cc(F, G) + cc(H)*, since we can always compute *(F, G)* in an optimal fashion first, then compute *H* optimally afterwards.

(Technically, this assumes that in our model both players always know when a communication protocol halts, so that they can combine two protocols sequentially without any additional overhead. No big deal, though.)

Now, a little further thought reveals thatâ€¦ well, there really *aren't* any other obvious, general constraints on the joint complexity! Let's call ** C** an

*Economic Cost Function (ECF)*if it obeys constraints 1-3. We are tempted to conjecture that perhaps

*every*ECF is in fact equal to the joint complexity (in the communication model) of

*some*particular collection of functions.

There are two things wrong with this conjecture. First, it's false, as can be seen by a simple counterexample: namely, the "buy-one-get-one-free" example, with *T* set to 1. That's how I stumbled onto this example, and is one reason why I find it interesting.

However, if we relax the problem, and just ask to realize some *scalar multiple* of ** C** as a joint complexity function, this counterexample loses its force.

The second thing wrong with the conjecture (in its relaxed form) is that, even if true, it'd likely be impossible to prove. This is because determining the *exact* computational cost of even modestly-complicated tasks is just way too hard. So I propose a doubly-relaxed form of the conjecture: I conjecture that if ** C** is an ECF, then there is a joint complexity function that is a good

*pointwise approximation*to some scalar multiple of

**. (Here we allow a**

*C**(1 +- eps)*multiplicative error.)

In my paper, I managed to prove the corresponding conjecture for the model of decision trees (aka deterministic query algorithms). Several interesting ingredients were needed for the proof. Now, why do I believe the conjecture should also hold true for the communication model? In a nutshell, I think it should be possible to 'embed' tasks in the query model into the communication model, by a suitable distributed encoding of each bit, in such a way that the relative costs of all computational tasks are approximately preserved. If this could be shown, the result in the communication model would follow from my result for decision trees. (See the paper for more details.)

We may not be ready for an attack on the general conjecture, however. In particular, we *seem* to require a much better understanding of so-called 'Direct Sum problems' in communication complexity. Thus, I offer the 'buy-one-get-one-free conjecture' as a simpler, more concrete problem on which we can hope to make progress sooner.

In the decision tree model, my result allows us to realize an ECF of the 'buy-one-get-one-free' type as a joint complexity function; but I *don't* know of any method for this that's significantly simpler than my general construction. Even finding such a simpler method in the decision tree model would be a very nice contribution, and might lead to new ideas for the more general problem.

Labels: complexity