Alexander A. Sherstov

In a breakthrough result, Razborov (2003) gave optimal

lower bounds on the communication complexity of every function f

of the form f(x,y)=D(|x AND y|) for some D:{0,1,...,n}->{0,1}, in

the bounded-error quantum model with and without prior entanglement.

This was proved by the _multidimensional_ discrepancy method. We

give an entirely ...
more >>>

Henning Wunderlich, Stefan Arnold

We introduce a new lower bound method for bounded-error quantum communication complexity,

the \emph{singular value method (svm)}, based on sums of squared singular values of the

communication matrix, and we compare it with existing methods.

The first finding is a constant factor improvement of lower bounds based on the

spectral ...
more >>>

Bo'az Klartag, Oded Regev

In STOC 1999, Raz presented a (partial) function for which there is a quantum protocol

communicating only $O(\log n)$ qubits, but for which any classical (randomized, bounded-error) protocol requires $\poly(n)$ bits of communication. That quantum protocol requires two rounds of communication. Ever since Raz's paper it was open whether the ...
more >>>

Alexander A. Sherstov

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^{-\Omega(n)}.$ We prove that quantum communication complexity obeys an SDPT whenever the communication lower bound for a single instance is proved by ... more >>>

Mark Braverman, Ankit Garg, Young Kun Ko, Jieming Mao, Dave Touchette

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)$ on the communication required for computing disjointness of input size $n$, which is optimal up to logarithmic factors. The previous best lower bound ... more >>>

Zi-Wen Liu, Christopher Perry, Yechao Zhu, Dax Enshan Koh, Scott Aaronson

We prove the existence of (one-way) communication tasks with a subconstant versus superconstant asymptotic gap, which we call "doubly infinite," between their quantum information and communication complexities. We do so by studying the exclusion game [C. Perry et al., Phys. Rev. Lett. 115, 030504 (2015)] for which there exist instances ... more >>>

Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika G\"o{\"o}s, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha

While exponential separations are known between quantum and randomized communication complexity for partial functions, e.g. Raz [1999], the best known separation between these measures for a total function is quadratic, witnessed by the disjointness function. We give the first super-quadratic separation between quantum and randomized

communication complexity for a ...
more >>>

Mark Bun, Justin Thaler

The approximate degree of a Boolean function $f \colon \{-1, 1\}^n \rightarrow \{-1, 1\}$ is the least degree of a real polynomial that approximates $f$ pointwise to error at most $1/3$. We introduce a generic method for increasing the approximate degree of a given function, while preserving its computability by ... more >>>

Anurag Anshu, Naresh Boddu, Dave Touchette

In a recent breakthrough result, Chattopadhyay, Mande and Sherif [ECCC TR18-17] showed an exponential separation between the log approximate rank and randomized communication complexity of a total function $f$, hence refuting the log approximate rank conjecture of Lee and Shraibman [2009]. We provide an alternate proof of their randomized communication ... more >>>