We give a direct product theorem for the entanglement-assisted interactive quantum communication complexity of an l-player predicate V. In particular we show that for a distribution p that is product across the input sets of the l players, the success probability of any entanglement-assisted quantum communication protocol for computing n ... more >>>
We prove a direct product theorem for the one-way entanglement-assisted quantum communication complexity of a general relation f\subseteq\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}. For any \varepsilon, \zeta > 0 and any k\geq1, we show that
Let f:\{0,1\}^n \rightarrow \{0,1\} be a Boolean function. The certificate complexity C(f) is a complexity measure that is quadratically tight for the zero-error randomized query complexity R_0(f): C(f) \leq R_0(f) \leq C(f)^2. In this paper we study a new complexity measure that we call expectational certificate complexity EC(f), which is ... more >>>
Let the randomized query complexity of a relation for error probability \epsilon be denoted by \R_\epsilon(\cdot). We prove that for any relation f \subseteq \{0,1\}^n \times \mathcal{R} and Boolean function g:\{0,1\}^m \rightarrow \{0,1\}, \R_{1/3}(f\circ g^n) = \Omega(\R_{4/9}(f)\cdot\R_{1/2-1/n^4}(g)), where f \circ g^n is the relation obtained by composing f and g. ... more >>>
We show that for any (partial) query function f:\{0,1\}^n\rightarrow \{0,1\}, the randomized communication complexity of f composed with \mathrm{Index}^n_m (with m= \poly(n)) is at least the randomized query complexity of f times \log n. Here \mathrm{Index}_m : [m] \times \{0,1\}^m \rightarrow \{0,1\} is defined as \mathrm{Index}_m(x,y)= y_x (the xth bit ... more >>>
We exhibit an n-node graph whose independent set polytope requires extended formulations of size exponential in \Omega(n/\log n). Previously, no explicit examples of n-dimensional 0/1-polytopes were known with extension complexity larger than exponential in \Theta(\sqrt{n}). Our construction is inspired by a relatively little-known connection between extended formulations and (monotone) circuit ... more >>>
Let f : \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\} be a 2-party function. For every product distribution \mu on \{0,1\}^n \times \{0,1\}^n, we show that
Does the information complexity of a function equal its communication complexity? We examine whether any currently known techniques might be used to show a separation between the two notions. Recently, Ganor et al. provided such a separation in the distributional setting for a specific input distribution ?. We show that ... more >>>
Common information was introduced by Wyner as a measure of dependence of two
random variables. This measure has been recently resurrected as a lower bound on the logarithm of the nonnegative rank of a nonnegative matrix. Lower bounds on nonnegative rank have important applications to several areas such
as communication ...
more >>>
We give a simpler proof, via query elimination, of a result due to O'Donnell, Saks, Schramm and Servedio, which shows a lower bound on the zero-error randomized query complexity of a function f in terms of the maximum influence of any variable of f. Our lower bound also applies to ... more >>>