Difference between revisions of "Open Problems:72"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
(Updating header)
 
(2 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
{{Header
 
{{Header
|title=Communication Complexity of approximating Set-Intersection Join
 
 
|source=baltimore16
 
|source=baltimore16
 
|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)$.
+
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})$ (for probability of error $\delta$?)
+
What is the two-way randomized communication complexity $R_\delta(\mathrm{SIJ}_{n,\varepsilon})$ (where $\delta$ is the probability of error)?
  
What is known {{cite|GuchtWWZ-15}}:
+
Known facts {{cite|GuchtWWZ-15}}:
  
- $R^{\to}_{1/n}(\mathrm{SIJ}_{n,\varepsilon}) = \tilde{O}(\frac{n}{\varepsilon^2})$ (one-way communication)
+
* $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$.
+
* $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$?
 
What is the right dependence on $\varepsilon$?
  
'''Note:''' $\mathrm{SIJ}$ stands for "Set-Intersection Join," which is the motivation for this question.
+
'''Note:''' $\mathrm{SIJ}$ stands for “Set-Intersection Join,” which is the motivation for this question.

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.