Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > RANDOMIZED COMMUNICATION COMPLEXITY:
Reports tagged with Randomized Communication Complexity:
TR14-046 | 8th April 2014
Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff

#### Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound

We consider two known lower bounds on randomized communication complexity: The smooth rectangle bound and the logarithm of the approximate non-negative rank. Our main result is that they are the same up to a multiplicative constant and a small additive term.
The logarithm of the nonnegative rank is known to ... more >>>

TR15-139 | 25th August 2015
Eli Ben-Sasson, Gal Maor

#### Lower bound for communication complexity with no public randomness

We give a self contained proof of a logarithmic lower bound on the communication complexity of any non redundant function, given that there is no access to shared randomness. This bound was first stated in Yao's seminal paper [STOC 1979], but no full proof appears in the literature.

Our proof ... more >>>

TR17-054 | 22nd March 2017
Anurag Anshu, Naresh Goud, Rahul Jain, Srijita Kundu, Priyanka Mukhopadhyay

#### Lifting randomized query complexity to randomized communication complexity

Revisions: 3

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 $x$th bit ... more >>>

ISSN 1433-8092 | Imprint