Short description: Communication complexity right from its advent in late 70's has been a very active area of research in Theoretical Computer Science. It is one area with very significant and far reaching connections with other areas of complexity theory. This projects intends to explore this area more both in the classical and quantum settings and attempts to attack some of the key questions still remaining open and possibly discover other interesting connections with other areas of complexity theory. This project includes in its scope studying other aspects of classical and quantum communication which do not fall under the umbrella of communication complexity e.g. Remote State Preparation etc.

Details: We will present background on some specific questions that we wish to investigate further.

1. One natural question that remains open is the "Direct Product" conjecture for randomized (worst case bounded error) public coin classical communication complexity and for entanglement assisted (worst case bounded error) quantum communication complexity. Roughly speaking the conjecture states that if for computing k copies of a function f with (appropriate) communication complexity say c, communication less than kc is provided, the success drops down exponentially in k. There has been some interesting progress lately. A weaker conjecture called the "Direct Sum" has been shown to be true for one-way public coin classical and entanglement assisted quantum communication complexity by Jain, Radhakrishnan and Sen [JRS05]. Direct sum states that if constant success is required for computing k copies of f then kc communication is required. [JRS05] showed that Direct Sum holds in fact for all relations as well for the described complexities. In the two-way case Harsha, Jain, McAllester and Radhakrishnan [HJMR07] (building on a result due to Jain, Radhakrishnan and Sen [JRS03]) have shown that Direct Sum holds for the two-way classical distributional communication complexity under product distributions. For the Direct Product conjecture also there has been interesting progress lately. It has been largely attacked and settled for product distributions in various settings of classical communication, however non-product distributions are proving to be a tough nut to crack. Jain, Klauck, Nayak [JKN08] have shown that the Direct Product holds, for all relations, for a complexity measure called as the "sub-distribution bound" (which is intimately connected to the randomized public coin communication complexity) under product distributions, both in the one-way and two-way classical models. Their result generalized and extended on a related result due to Beame, Pitassi, Segerlind and Wigderson [BPSW07] in the two-way case. [JKN08] have also shown "Weak Direct Product" results for sub-distribution bounds, for all relations, for the two-way case both under product and non-product distributions. A Weak Direct Product result states that if communication less than c is provided for k copies of f then the success goes down exponentially in k. In the quantum setting the Direct Product question is widely open in most settings. Recently Ben-Aroya, Regev and de Wolf [BARdW07] have shown that Direct Product holds for one-way quantum communication complexity of a specific, well used, function called the Random Access Codes.
2. Another question that is widely open is trying to show separation between quantum and classical communication complexities for total functions. In contrast to the case of relations and partial functions in which strong exponential advantage has been exhibited for quantum protocols, the best separation known for total functions is quadratic in the two-way case and no-asymptotic separation in the one-way case. Due to the lack of better separation exhibited, researchers are strongly conjecturing that these are the best possible. Recently new upper bounds on one-way classical communication complexity and new lower bounds on one-way quantum communication complexity have been shown by Jain and Zhang [JZ08] with intention to bridge the gap between classical and quantum complexities so as to possibly prove no separation. Their upper bound extends the well known upper bound of Kremer, Nisan and Ron [KNR95], and bounds the distributional one-way communication complexity for functions, under a given non-product distribution in terms of their VC dimension and the "mutual information" under the given distribution. They also lower bound the distributional quantum communication complexity for total and partial functions under a given product distribution in terms of the "rectangle bound" under the given distribution. This lower bound along with a tight relation between rectangle bound and dististributional complexity under product distributions shown by [JKN08], implies that there is no-separation between quantum and classical distributional complexities for total and partial function under product distribution. This no-separation under product distributions was previously known only for boolean functions. The quantum lower bound of [JZ08] also implied that every boolean classical extractor is also a good quantum extractor. This result was previously known due to [KT08] where it was shown using properties of the so called "pretty good measurement". If the lower bound of [JZ08] also applied to non-product distribution then it would have implied that the quantum public coin complexity would be equal to classical public coin complexity due to a Yao [Y77] like connection shown by [JKN08] between one-way rectangle bounds and randomized public coin communication complexity. However unfortunately this is not true as is implicit in the work of Gavinsky, Kempe, Kerenedis, Raz, de Wolf [GKKRdW07]. Also recently Zhang [Z08] exhibited that no known technique to bound quantum communication complexity is tight for all functions. So new techniques might be needed to be discovered so as to attack the no-separation conjecture in the one-way case.
3. The third problem that we wish to investigate concerns studying the role of entanglement in quantum communication protocols. It is a big open question as to how much entanglement is enough in quantum communication protocols with the best possible communication usage. For classical protocols this question was answered long time back by Newman [N96] when he showed that O(log n) bits of shared randomness is enough for computing any function or relation with n bits of inputs. In contrast the best known bound for quantum protocols is "Infinity" ! Jain, Radhakrishnan and Sen [JRS05] have however shown the Newman's style black-box reduction is not possible with quantum protocols. Newman's reduction was black-box in the sense that it did not require the communicating parties to change their actions while the protocol was transformed to use only O(log n) bits of randomness. Recently Jain, Klauck, Nayak [JKN08] and Gavinsky [G07] have shown that there are protocols for some relations for which the communication requirement shoots up exponentially if the entanglement used is reduced even by a multiplicative log factor. There is recently a result due to Leung, Toner, Watrous [LTW08] in which they show that there is a sequence of distributed tasks that require more and more entanglement which in the limit goes to infinity.

Progress

Direct Sum and Direct Product results in different models and settings of communication complexity have been shown. They roughly state that the resources required for computing k-copies together are k-times the resources required for one instance of the problem. These results appear in the papers titled: "New Results in the Simultaneous Message Passing Model", "Direct product theorems for classical communication complexity via sub-distribution bounds", "A Strong Direct Product Theorem for Disjointness". Similar results have also been obtained in the area of query complexity in the paper titled: "Optimal Direct Sum Results for Deterministic and Randomized Decision Tree Complexity".

Publications

Pre-Prints

References

Back