A strong direct product theorem says that if we want to compute k independent instances of a function, using less than times the resources needed for one instance, then our overall success probability will be exponentially small in k. We establish such theorems classical as well quantum query complexity OR‐function. This implies slightly weaker results all total functions. prove similar result communication protocols computing disjointness function. Our imply time‐space tradeoff...

Motivated by the increasing need for fast distributed processing of large-scale graphs such as Web graph and various social networks, we study a number fundamental problems in message-passing model, where have k machines that jointly perform computation on an arbitrary n-node (typically, n > k) input graph. The is assumed to be randomly partitioned among ≥ 2 (a common implementation many real world systems). communication point-to-point, goal minimize time complexity i.e., rounds, solving...

We describe new lower bounds for randomized communication complexity and query which we call the partition bounds. They are expressed as optimum value of linear programs. For show that bound is stronger than both rectangle/corruption γ2/generalized discrepancy In model approximate polynomial degree classical adversary also exhibit an example where quadratically larger

A strong direct product theorem states that if we want to compute k independent instances of a function, using less than times the resources needed for one instance, then overall success probability will be exponentially small in k. We establish such randomized communication complexity Disjointness problem, i.e., with const• kn solving size n can only This solves an open problem [KSW07, LSS08]. also show this bound even holds $AM$-communication protocols limited ambiguity. The main result...

We investigate the power of most important lower bound technique in randomized communication complexity, which is based on an evaluation maximal size approximately monochromatic rectangles, with respect to arbitrary distributions inputs. While it known that 0-error version this polynomially tight for deterministic communication, nothing direction constant error and complexity. first study a one-sided obtain its value lies between MA- AM- complexities considered function. Hence actually works...

Article Free Access Share on On quantum and probabilistic communication: Las Vegas one-way protocols Author: Hartmut Klauck Johann Wolfgang Goethe-Universität Frankfurt, 60054 Frankfurt am Main, Germany GermanyView Profile Authors Info & Claims STOC '00: Proceedings of the thirty-second annual ACM symposium Theory computingMay 2000Pages 644–651https://doi.org/10.1145/335305.335396Published:01 May 2000Publication History 47citation576DownloadsMetricsTotal Citations47Total Downloads576Last 12...

We prove lower bounds on the bounded error quantum communication complexity. Our methods are based Fourier transform of considered functions. First we generalize a method for proving classical complexity developed by Raz [Comput. Complexity, 5 (1995), pp. 205–221] to case. Applying this method, give an exponential separation between and nondeterministic develop several other bound transform, notably showing that $\sqrt{\bar{s}(f)/\log n}$, average sensitivity $\bar{s}(f)$ function f, yields...

One of the most intriguing facts about communication using quantum states is that these cannot be used to transmit more classical bits than number qubits used, yet in some scenarios there are ways conveying information with exponentially fewer possible classically [3, 26]. Moreover, methods have a very simple structure---they involve only few message exchanges between communicating parties.

Motivated by the increasing need for fast distributed processing of large-scale graphs such as Web graph and various social networks, we study a number fundamental problems in message-passing model, where have k machines that jointly perform computation on an arbitrary n-node (typically, n ≫ k) input graph. The is assumed to be randomly partitioned among ≥ 2 (a common implementation many real world systems). communication point-to-point, goal minimize time complexity, i.e., rounds, solving...

The focus of this paper is on quantum distributed computation, where we investigate whether communication can help in speeding up network algorithms. Our main result that for certain fundamental problems such as minimum spanning tree, cut, and shortest paths, does not substantially algorithms these compared to the classical setting.

In some scenarios there are ways of conveying information with many fewer, even exponentially qubits than possible classically [1], [2], [3].Moreover, these methods have a very simple structurethey involve only few message exchanges between the communicating parties.It is therefore natural to ask whether every classical protocol may be transformed "simpler" quantum protocol-one that has similar efficiency, but uses fewer exchanges.We show for any constant k, problem such its k+1...

We show several results related to interactive proof modes of communication complexity. First we lower bounds for the QMA-communication complexity functions Inner Product and Disjointness. describe a general method prove complexity, how one can 'transfer' hardness under an analogous measure in query model using Sherstov's pattern matrix method.Combining result by Vereshchagin find partial function with AM-communication O(log n), PP-communication Ω(n <sup...

We prove new lower bounds for bounded error quantum communication complexity. Our methods are based on the Fourier transform of considered functions. First we generalize a method proving classical complexity developed by Raz to case. Applying this give an exponential separation between and nondeterministic develop several other bound transform, notably showing that \sqrt{\bar{s}(f)/\log n}, average sensitivity \bar{s}(f) function f, yields f(x AND y XOR z), where x is Boolean word held Alice...

A basic question in complexity theory is whether the computational resources required for solving k independent instances of same problem scale as times one instance. We investigate this various models classical communication complexity. introduce a new measure, subdistribution bound , which relaxation well-studied rectangle or corruption nonetheless show that Boolean functions with constant error, latter up to factor. prove one-way version tightly captures public-coin randomized any...

This paper surveys the field of quantum communication complexity. Some interesting recent results are collected concerning relations to classical communication, lower bound methods, one-way and applications

A strong direct product theorem says that if we want to compute k independent instances of a function, using less than times the resources needed for one instance, then our overall success probability is exponentially small in k. We establish such theorems classical as well quantum query complexity OR function. This implies slightly weaker results all total functions. prove similar result communication protocols computing disjointness These imply time-space tradeoff T/sup 2/S = /spl...

In this paper the Nečiporuk method for proving lower bounds on size of Boolean formulas is reformulated in terms one-way communication complexity. We investigate settings probabilistic formulas, nondeterministic and quantum formulas. all cases we can use results about complexity to prove formula size. The main regarding are as follows: show a polynomial gap between probabilistic/quantum deterministic near-quadratic sizes with limited access bits slightly more such bits, bound Furthermore...

We define a new model of data streaming algorithms that employ prover/helper to outsource difficult computations in verifiable way. While for the verifier usual time (per symbol read) and space constraints are place, prover has unbounded space. Both parties cannot look into future (i.e., do not know arriving later). Previous work on such models either severely restricted total communication between verifier, or extended computation by long annotation be streamed from offline after original...

Consider the following simultaneous message passing (SMP) model for computing a relation f sube X times Y Z. In this Alice, on input x isin and Bob, y Y, send one each to third party Referee who then outputs z Z such that (x, y, z) f. We first show optimal direct sum results all relations / in model, both quantum classical settings, situation where we allow shared resources (shared entanglement protocols public coins protocols) between Alice Bob no resource Bob. This implies that,...

We prove new lower bounds for bounded error quantum communication complexity. Our methods are based on the Fourier transform of considered functions. First we generalize a method proving classical complexity developed by R. Raz (1995) to case. Applying this give an exponential separation between and nondeterministic develop several other bound methods, notably showing that /spl radic/(s~(f)/log n) n, average sensitivity s~(f) function f, yields f (x/spl and/y/spl oplus/yz), where x is...

We investigate the complexity of sorting in model sequential quantum circuits. While it is known that general a algorithm based on comparisons alone cannot outperform classical algorithms by more than constant factor time complexity, this wrong space bounded setting. observe for all storage bounds n/log ≥ S log3n, one can devise sorts n numbers (using only) T=O(n3/2 log3/2 n/√S). then show following lower bound time-space tradeoff from polynomial size range (not necessarily comparisons):...

A strong direct product theorem says that if we want to compute k independent instances of a function, using less than times the resources needed for one instance, then our overall success probability will be exponentially small in k. We establish such theorems classical as well quantum query complexity OR function. This implies slightly weaker results all total functions. prove similar result communication protocols computing Disjointness Our imply time-space tradeoff T^2*S=Omega(N^3)...