On the communication complexity of co-linearity problems

In the k-party simultaneous message model, k - 1 parties holding respectively x₁, x₂, ⋯, x_k-1 wish to compute the value of some boolean function f(x₁, x ₂,...,x_k-1), by each sending a stochastically chosen message to a k-th party, the referee, who then decides on the value of f with probability at least 2/3 of being correct. Let R^∥(f) be the minimum number of total communication bits needed to compute f by any such algorithm. The (k, n)-Co-Linearity Problem is defined by CL_k,n(x ₁, x₂,..., x_k-1) = 1, if and only if ⊕_1≤i≤k-1x_i = 0ⁿ (where x _i are n-bit strings). It is well known that, for any fixed k ≥ 3, R^∥(CL_k,n) = O(n^(k-2)/(k-1)), and that the bound is tight for k = 3. It is an interesting open question whether the bound is tight for k > 3. In this talk we present some new results on this question. Specifically, we prove that the above bound is tight in the linear model, in which all the transmitted message bits are linear functions of the input bits. We also discuss CL_k,n's quantum communication complexity, which also has received considerable attention in recent years.