# Difference between revisions of "Open Problems:72"

m (Krzysztof Onak moved page Waiting:Qin to Open Problems:72 without leaving a redirect: Moving to main list of problems) |
(Updating header) |
||

Line 1: | Line 1: | ||

{{Header | {{Header | ||

− | |||

|source=baltimore16 | |source=baltimore16 | ||

|who=Qin Zhang | |who=Qin Zhang |

## Latest revision as of 18:43, 18 January 2016

Suggested by | Qin Zhang |
---|---|

Source | Baltimore 2016 |

Short link | https://sublinear.info/72 |

For $\varepsilon\in(0,1]$ and $n\geq 1$, consider the following communication complexity problem $\mathrm{SIJ}_{n,\varepsilon}$: Alice and Bob are given matrices $A,B\in\{0,1\}^{n\times n}$, respectively, and wish to output a $(1+\varepsilon)$-approximation to the number of non-zero entries in the product $C=AB$. What is the two-way randomized communication complexity $R_\delta(\mathrm{SIJ}_{n,\varepsilon})$ (where $\delta$ is the probability of error)?

Known facts [GuchtWWZ-15]:

- $R^{\to}_{1/n}(\mathrm{SIJ}_{n,\varepsilon}) = \tilde{O}(\frac{n}{\varepsilon^2})$ (one-way communication),

- $R_\delta(\mathrm{SIJ}_{n,\varepsilon}) = \Omega(\frac{n}{\varepsilon^{2/3}})$ for some absolute constant $\delta > 0$.

What is the right dependence on $\varepsilon$?

**Note:** $\mathrm{SIJ}$ stands for “Set-Intersection Join,” which is the motivation for this question.