Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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: 4

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 >>>

TR18-176 | 26th October 2018
Arkadev Chattopadhyay, Nikhil Mande, Suhail Sherif

The Log-Approximate-Rank Conjecture is False

We construct a simple and total XOR function $F$ on $2n$ variables that has only $O(\sqrt{n})$ spectral norm, $O(n^2)$ approximate rank and $n^{O(\log n)}$ approximate nonnegative rank. We show it has polynomially large randomized bounded-error communication complexity of $\Omega(\sqrt{n})$. This yields the first exponential gap between the logarithm of the ... more >>>

TR20-184 | 10th December 2020
Dmitry Itsykson, Artur Riazanov

Proof complexity of natural formulas via communication arguments

A canonical communication problem ${\rm Search}(\phi)$ is defined for every unsatisfiable CNF $\phi$: an assignment to the variables of $\phi$ is distributed among the communicating parties, they are to find a clause of $\phi$ falsified by this assignment. Lower bounds on the randomized $k$-party communication complexity of ${\rm Search}(\phi)$ in ... more >>>

ISSN 1433-8092 | Imprint