Difference between revisions of "Open Problems:72"
(Created page with "{{Header |title=Title of the problem |source=baltimore16 |who=Qin Zhang }} The open problem will appear here.") |
|||
| Line 4: | Line 4: | ||
|who=Qin Zhang | |who=Qin Zhang | ||
}} | }} | ||
| − | + | For $\varepsilon\in(0,1]$ and $n\geq 1$, consider the following communication complexity problem $\mathrm{SIJ}_{n,\varepsilon}$: Alice and Bob are respectively given matrices $A,B\in\{0,1\}^{n\times n}$, and wish to approximate the number of non-zero elements of the product $C=AB$: i.e., to output an $(1+\varepsilon)$-approximation of $\operatorname{nnz}(C)$. | |
| + | What is the two-way randomized communication complexity $R_\delta(\mathrm{SIJ}_{n,\varepsilon})$ (for probability of error $\delta$?) | ||
| + | |||
| + | What is known {{cite|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. | ||
Revision as of 21:02, 10 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 respectively given matrices $A,B\in\{0,1\}^{n\times n}$, and wish to approximate the number of non-zero elements of the product $C=AB$: i.e., to output an $(1+\varepsilon)$-approximation of $\operatorname{nnz}(C)$. What is the two-way randomized communication complexity $R_\delta(\mathrm{SIJ}_{n,\varepsilon})$ (for probability of error $\delta$?)
What is known [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.
