New bounds on classical and quantum one-way communication complexity

摘要

The main goal of this work is to show bounds for general total functions instead of specific ones, with the motivation of approaching the conjecture of R{sup}(1, pub)(f) = O(Q{sup}(1, pub)(f)) mentioned in Section 1. In the wake of our quantum lower bound result, it is natural to ask whether in the two-way model also, there is a similar relationship between quantum distributional communication complexity of a function f, under product distributions, and the corresponding rectangle bound. Further explorations along this approach are expected. For example, concerning the classical upper bound, a natural question to ask is whether the bound could be tightened, especially in terms of its dependence on the mutual information I (X: Y) between the inputs, under a given non-product distribution. Is it actually true that (D{sub}ε){sup}(1,μ){sup}=O(I(X:Y) + VC(f))? Also, can we say more on the quantum lower bound result for non-product distributions.