Abstract:
Consider the "Number in Hand" multiparty communication complexity model, where k players holding inputs x_1,...,x_k in {0,1}^n communicate to compute the value f(x_1,...,x_k) of a function f known to all of them. The main lower bound technique for the communication complexity of such problems is that of partition arguments: partition the k players into two disjoint sets of players and find a lower bound for the induced two-party communication complexity problem. In this paper, we study the power of partition arguments. Our two main results are very different in nature: (i) For randomized communication complexity, we show that partition arguments may yield bounds that are exponentially far from the true communication complexity. Specifically, we prove that there exists a 3-argument function f whose communication complexity is Omega(n), while partition arguments can only yield an Omega(log n) lower bound. The same holds for nondeterministic communication complexity. (ii) For deterministic communication complexity, we prove that finding significant gaps between the true communication complexity and the best lower bound that can be obtained via partition arguments, would imply progress on a generalized version of the "log-rank conjecture" in communication complexity. We conclude with two results on the multiparty "fooling set technique", another method for obtaining communication complexity lower bounds.

Abstract:
Quantum entanglement cannot be used to achieve direct communication between remote parties, but it can reduce the communication needed for some problems. Let each of k parties hold some partial input data to some fixed k-variable function f. The communication complexity of f is the minimum number of classical bits required to be broadcasted for every party to know the value of f on their inputs. We construct a function G such that for the one-round communication model and three parties, G can be computed with n+1 bits of communication when the parties share prior entanglement. We then show that without entangled particles, the one-round communication complexity of G is (3/2)n + 1. Next we generalize this function to a function F. We show that if the parties share prior quantum entanglement, then the communication complexity of F is exactly k. We also show that if no entangled particles are provided, then the communication complexity of F is roughly k*log(k). These two results prove for the first time communication complexity separations better than a constant number of bits.

Abstract:
We prove new bounds on the quantum communication complexity of the disjointness and equality problems. For the case of exact and non-deterministic protocols we show that these complexities are all equal to n+1, the previous best lower bound being n/2. We show this by improving a general bound for non-deterministic protocols of de Wolf. We also give an O(sqrt{n}c^{log^* n})-qubit bounded-error protocol for disjointness, modifying and improving the earlier O(sqrt{n}log n) protocol of Buhrman, Cleve, and Wigderson, and prove an Omega(sqrt{n}) lower bound for a large class of protocols that includes the BCW-protocol as well as our new protocol.

Abstract:
We prove that NP differs from coNP and coNP is not a subset of MA in the number-on-forehead model of multiparty communication complexity for up to k = (1-\epsilon)log(n) players, where \epsilon>0 is any constant. Specifically, we construct a function F with co-nondeterministic complexity O(log(n)) and Merlin-Arthur complexity n^{\Omega(1)}. The problem was open for k > 2.

Abstract:
We define a quantum model for multiparty communication complexity and prove a simulation theorem between the classical and quantum models. As a result of our simulation, we show that if the quantum k-party communication complexity of a function f is $\Omega(n/2^k)$, then its classical k-party communication is $\Omega(n/2^{k/2})$. Finding such an f would allow us to prove strong classical lower bounds for (k>log n) players and hence resolve a main open question about symmetric circuits. Furthermore, we prove that for the Generalized Inner Product (GIP) function, the quantum model is exponentially more efficient than the classical one. This provides the first exponential separation for a total function between any quantum and public coin randomized communication model.

Abstract:
There are three different types of nondeterminism in quantum communication: i) $\nqp$-communication, ii) $\qma$-communication, and iii) $\qcma$-communication. In this \redout{paper} we show that multiparty $\nqp$-communication can be exponentially stronger than $\qcma$-communication. This also implies an exponential separation with respect to classical multiparty nondeterministic communication complexity. We argue that there exists a total function that is hard for $\qcma$-communication and easy for $\nqp$-communication. The proof of it involves an application of the pattern tensor method and a new lower bound for polynomial threshold degree. Another important consequence of this result is that nondeterministic rank can be exponentially lower than the discrepancy bound.

Abstract:
In this paper we study the two player randomized communication complexity of the sparse set disjointness and the exists-equal problems and give matching lower and upper bounds (up to constant factors) for any number of rounds for both of these problems. In the sparse set disjointness problem, each player receives a k-subset of [m] and the goal is to determine whether the sets intersect. For this problem, we give a protocol that communicates a total of O(k\log^{(r)}k) bits over r rounds and errs with very small probability. Here we can take r=\log^{*}k to obtain a O(k) total communication \log^{*}k-round protocol with exponentially small error probability, improving on the O(k)-bits O(\log k)-round constant error probability protocol of Hastad and Wigderson from 1997. In the exist-equal problem, the players receive vectors x,y\in [t]^n and the goal is to determine whether there exists a coordinate i such that x_i=y_i. Namely, the exists-equal problem is the OR of n equality problems. Observe that exists-equal is an instance of sparse set disjointness with k=n, hence the protocol above applies here as well, giving an O(n\log^{(r)}n) upper bound. Our main technical contribution in this paper is a matching lower bound: we show that when t=\Omega(n), any r-round randomized protocol for the exists-equal problem with error probability at most 1/3 should have a message of size \Omega(n\log^{(r)}n). Our lower bound holds even for super-constant r <= \log^*n, showing that any O(n) bits exists-equal protocol should have \log^*n - O(1) rounds.

Abstract:
We prove a near optimal round-communication tradeoff for the two-party quantum communication complexity of disjointness. For protocols with $r$ rounds, we prove a lower bound of $\tilde{\Omega}(n/r + r)$ on the communication required for computing disjointness of input size $n$, which is optimal up to logarithmic factors. The previous best lower bound was $\Omega(n/r^2 + r)$ due to Jain, Radhakrishnan and Sen [JRS03]. Along the way, we develop several tools for quantum information complexity, one of which is a lower bound for quantum information complexity in terms of the generalized discrepancy method. As a corollary, we get that the quantum communication complexity of any boolean function $f$ is at most $2^{O(QIC(f))}$, where $QIC(f)$ is the prior-free quantum information complexity of $f$ (with error $1/3$).

Abstract:
We consider the class of functions whose value depends only on the intersection of the input X_1,X_2, ..., X_t; that is, for each F in this class there is an f_F: 2^{[n]} \to {0,1}, such that F(X_1,X_2, ..., X_t) = f_F(X_1 \cap X_2 \cap ... \cap X_t). We show that the t-party k-round communication complexity of F is Omega(s_m(f_F)/(k^2)), where s_m(f_F) stands for the `monotone sensitivity of f_F' and is defined by s_m(f_F) \defeq max_{S\subseteq [n]} |{i: f_F(S \cup {i}) \neq f_F(S)|. For two-party quantum communication protocols for the set disjointness problem, this implies that the two parties must exchange Omega(n/k^2) qubits. For k=1, our lower bound matches the Omega(n) lower bound observed by Buhrman and de Wolf (based on a result of Nayak, and for 2 <= k <= n^{1/4}, improves the lower bound of Omega(sqrt{n}) shown by Razborov. (For protocols with no restrictions on the number of rounds, we can conclude that the two parties must exchange Omega(n^{1/3}) qubits. This, however, falls short of the optimal Omega(sqrt{n}) lower bound shown by Razborov.)

Abstract:
In a multiparty message-passing model of communication, there are $k$ players. Each player has a private input, and they communicate by sending messages to one another over private channels. While this model has been used extensively in distributed computing and in multiparty computation, lower bounds on communication complexity in this model and related models have been somewhat scarce. In recent work \cite{phillips12,woodruff12,woodruff13}, strong lower bounds of the form $\Omega(n \cdot k)$ were obtained for several functions in the message-passing model; however, a lower bound on the classical Set Disjointness problem remained elusive. In this paper, we prove tight lower bounds of the form $\Omega(n \cdot k)$ for the Set Disjointness problem in the message passing model. Our bounds are obtained by developing information complexity tools in the message-passing model, and then proving an information complexity lower bound for Set Disjointness. As a corollary, we show a tight lower bound for the task allocation problem \cite{DruckerKuhnOshman} via a reduction from Set Disjointness.