Discrepancy is a versatile bound in communication complexity which can be used to show lower bounds in randomized, quantum, and even weakly-unbounded error models of communication. We show an optimal product theorem for discrepancy, namely that for any two Boolean functions f, g, disc(f odot g)=thetas(disc(f) disc(g)). As a consequence we obtain a strong direct product theorem for distributional complexity, and direct sum theorems for worst-case complexity, for bounds shown by the discrepancy method. Our results resolve an open problem of Shaltiel (2003) who showed a weaker product theorem for discrepancy with respect to the uniform distribution, discUodot(fodotk)=O(discU(f))k/3. The main tool for our results is semidefinite programming, in particular a recent characterization of discrepancy in terms of a semidefinite programming quantity by Linial and Shraibman (2006).
Discrepancy is a versatile bound in communication complexity which can be used to show lower bounds in randomized, quantum, and even weakly-unbounded error models of communication. We show an optimal product theorem for discrepancy, namely that for any two Boolean functions f, g, disc(f odot g)=thetas(disc(f) disc(g)). As a consequence we obtain a strong direct product theorem for distributional complexity, and direct sum theorems for worst-case complexity, for bounds shown by the discrepancy method. Our results resolve an open problem of Shaltiel (2003) who showed a weaker product theorem for discrepancy with respect to the uniform distribution, discUodot(fodotk)=O(discU(f))k/3. The main tool for our results is semidefinite programming, in particular a recent characterization of discrepancy in terms of a semidefinite programming quantity by Linial and Shraibman (2006).
A strong direct product theorem states that, in order to solve k instances of a problem, if we provide less than k times the resource required to compute one instance, then the probability of overall success is exponentially small in k. In this paper, we consider the model of two-way public-coin communication complexity and show a strong direct product theorem for all relations in terms of the smooth rectangle bound, introduced by Jain and Klauck as a generic lower bound method in this model. Our result therefore uniformly implies a strong direct product theorem for all relations for which an (asymptotically) optimal lower bound can be provided using the smooth rectangle bound, for example Inner Product, Greater-Than, Set-Disjointness, Gap-Hamming Distance etc. Our result also implies near optimal direct product results for several important functions and relations used to show exponential separations between classical and quantum communication complexity, for which near optimal lower bounds are provided using the rectangle bound, for example by Raz [1999], Gavinsky [2008] and Klartag and Regev [2011]. In fact we are not aware of any relation for which it is known that the smooth rectangle bound does not provide an optimal lower bound. This lower bound subsumes many of the other lower bound methods, for example the rectangle bound (a.k.a the corruption bound), the smooth discrepancy bound (a.k.a the γ_2 bound) which in turn subsumes the discrepancy bound, the subdistribution bound and the conditional min-entropy bound. We show our result using information theoretic arguments. A key tool we use is a sampling protocol due to Braverman [2012], in fact a modification of it used by Kerenidis, Laplante, Lerays, Roland and Xiao [2012].
We show two new direct product results in two different models of communication complexity. Our first result is in the one-way public-coin model. Let f ⊆ X × Y × Z be a relation and e > 0 be a constant. Let R1,pube(f) represent the communication complexity of f, with worst-case error e in this model. We show that if for computing fk (k independent copies of f) in this model, o(k c R1, pub1/3(f)) communication is used, then the success is exponentially small in k. We show a new tight characterization of communication complexity in this model which strengthens the tight characterization shown in Jain et al. [2008]. We use this new characterization to show our direct product result and this characterization may also be of independent interest.Our second direct product result is in the model of two-way public-coin communication complexity. We show a direct product result for all relations in this model in terms of a new complexity measure that we define. Our new measure is a generalization to nonproduct distributions, of the two-way product subdistribution bound of Jain et al. [2008]. Our direct product result therefore generalizes to nonproduct distributions, their direct product result in terms of the two-way product subdistribution bound. As an application of our new direct product result, we reproduce (via completely different arguments) strong direct product result for the set-disjointness problem which was previously shown by Klauck [2010]. We show this by proving that our new complexity measure gives a tight lower bound of Ω(n) for the set-disjointness problem on n-bit inputs (this strengthens the linear lower bound on the rectangle/corruption bound for set-disjointness shown by Razborov [1992]). In addition, we show that many previously known direct product results in this model are uniformly implied and often strengthened by our result.
A basic question in complexity theory is whether the computational resources required for solving k independent instances of the same problem scale as k times the resources required for one instance. We investigate this question in various models of classical communication complexity. We introduce a new measure, the subdistribution bound , which is a relaxation of the well-studied rectangle or corruption bound in communication complexity. We nonetheless show that for the communication complexity of Boolean functions with constant error, the subdistribution bound is the same as the latter measure, up to a constant factor. We prove that the one-way version of this bound tightly captures the one-way public-coin randomized communication complexity of any relation, and the two-way version bounds the two-way public-coin randomized communication complexity from below. More importantly, we show that the bound satisfies the strong direct product property under product distributions for both one- and two-way protocols, and the weak direct product property under arbitrary distributions for two-way protocols. These results subsume and strengthen, in a unified manner, several recent results on the direct product question. The simplicity and broad applicability of our technique is perhaps an indication of its potential to solve yet more challenging questions regarding the direct product problem.
We show two new direct product results in two different models of communication complexity. Our first result is in the one-way public-coin model. Let f ⊆ X × Y × Z be a relation and ϵ > 0 be a constant. Let R 1,pub ϵ ( f ) represent the communication complexity of f , with worst-case error ϵ in this model. We show that if for computing f k ( k independent copies of f ) in this model, o ( k ċ R 1, pub 1/3 ( f )) communication is used, then the success is exponentially small in k . We show a new tight characterization of communication complexity in this model which strengthens the tight characterization shown in Jain et al. [2008]. We use this new characterization to show our direct product result and this characterization may also be of independent interest. Our second direct product result is in the model of two-way public-coin communication complexity. We show a direct product result for all relations in this model in terms of a new complexity measure that we define. Our new measure is a generalization to nonproduct distributions, of the two-way product subdistribution bound of Jain et al. [2008]. Our direct product result therefore generalizes to nonproduct distributions, their direct product result in terms of the two-way product subdistribution bound. As an application of our new direct product result, we reproduce (via completely different arguments) strong direct product result for the set-disjointness problem which was previously shown by Klauck [2010]. We show this by proving that our new complexity measure gives a tight lower bound of Ω( n ) for the set-disjointness problem on n -bit inputs (this strengthens the linear lower bound on the rectangle/corruption bound for set-disjointness shown by Razborov [1992]). In addition, we show that many previously known direct product results in this model are uniformly implied and often strengthened by our result.
We give a direct product theorem for the entanglement-assisted interactive quantum communication complexity in terms of the quantum partition bound for product distributions. The quantum partition or efficiency bound is a lower bound on communication complexity, a non-distributional version of which was introduced by Laplante, Lerays and Roland (2012). For a two-input boolean function, the best result for interactive quantum communication complexity known previously was due to Sherstov (2018), who showed a direct product theorem in terms of the generalized discrepancy. While there is no direct relationship between the maximum distributional quantum partition bound for product distributions, and the generalized discrepancy method, unlike Sherstov's result, our result works for two-input functions or relations whose outputs are non-boolean as well. As an application of our result, we show that it is possible to do device-independent quantum key distribution (DIQKD) without the assumption that devices do not leak any information after inputs are provided to them. We analyze the DIQKD protocol given by Jain, Miller and Shi (2020), and show that when the protocol is carried out with devices that are compatible with several copies of the Magic Square game, it is possible to extract a linear (in the number of copies of the game) amount of key from it, even in the presence of a linear amount of leakage. Our security proof is parallel, i.e., the honest parties can enter all their inputs into their devices at once, and works for a leakage model that is arbitrarily interactive, i.e., the devices of the honest parties Alice and Bob can exchange information with each other and with the eavesdropper Eve in any number of rounds, as long as the total number of bits or qubits communicated is bounded.
A strong direct product theorem (SDPT) states that solving n instances of a problem requires Omega(n) times the resources for a single instance, even to achieve success probability 2-Ω(n). We prove that quantum communication complexity obeys an SDPT whenever the communication lower bound for a single instance is proved by the generalized discrepancy method, the strongest technique in that model. We prove that quantum query complexity obeys an SDPT whenever the query lower bound for a single instance is proved by the polynomial method, one of the two main techniques in that model. In both models, we prove the corresponding XOR lemmas and threshold direct product theorems.