Open Problems:72 - Revision history

Krzysztof Onak: Updating header

2016-01-18T18:43:05Z

Updating header

Krzysztof Onak: Krzysztof Onak moved page Waiting:Qin to Open Problems:72 without leaving a redirect: Moving to main list of problems

2016-01-18T18:39:15Z

Krzysztof Onak moved page Waiting:Qin to Open Problems:72 without leaving a redirect: Moving to main list of problems

Krzysztof Onak: Small edits

2016-01-12T21:50:56Z

Small edits

Ccanonne at 21:05, 10 January 2016

2016-01-10T21:05:20Z

Ccanonne at 21:02, 10 January 2016

2016-01-10T21:02:27Z

Krzysztof Onak: Created page with "{{Header |title=Title of the problem |source=baltimore16 |who=Qin Zhang }} The open problem will appear here."

2016-01-10T04:29:15Z

Created page with "{{Header |title=Title of the problem |source=baltimore16 |who=Qin Zhang }} The open problem will appear here."

New page

{{Header
|title=Title of the problem
|source=baltimore16
|who=Qin Zhang
}}
The open problem will appear here.

@@ Line 4: / Line 4: @@
 |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$?
-'''Note:''' $\mathrm{SIJ}$ stands for "Set-Intersection Join," which is the motivation for this question.
+'''Note:''' $\mathrm{SIJ}$ stands for &ldquo;Set-Intersection Join,&rdquo; which is the motivation for this question.

@@ Line 1: / Line 1: @@
 {{Header
 |source=baltimore16
 |who=Qin Zhang

← Older revision	Revision as of 18:39, 18 January 2016
(No difference)