Difference between revisions of "Open Problems:78"
(reference) |
(added Sanyal) |
||
| Line 3: | Line 3: | ||
|who=Grigory Yaroslavtsev | |who=Grigory Yaroslavtsev | ||
}} | }} | ||
| − | For a function $f:\{0,1\}^n\rightarrow\{0,1\}$, we define its deterministic linear sketch complexity $D^\text{lin}(f)$ as a the smallest number $k$ such that there exist $k$ sets $S_1,\ldots,S_k \subseteq [n]$ such that for any $x\in \{0,1\}^n$, we can compute $f(x)$ using $\sum_{i\in S_1} x_i, \ldots, \sum_{i\in S_k} x_i$, where the sum is mod $2$. For randomized linear sketch complexity, which is denoted by $R^\text{lin}(f)$, the $k$ sets are chosen in advance from a joint distribution and are available for recovering $f(x)$. Please see the paper by Kannan, Mossel, and Yaroslavtsev {{cite|KannanMSY-18}} for more details. | + | For a function $f:\{0,1\}^n\rightarrow\{0,1\}$, we define its deterministic linear sketch complexity $D^\text{lin}(f)$ as a the smallest number $k$ such that there exist $k$ sets $S_1,\ldots,S_k \subseteq [n]$ such that for any $x\in \{0,1\}^n$, we can compute $f(x)$ using $\sum_{i\in S_1} x_i, \ldots, \sum_{i\in S_k} x_i$, where the sum is mod $2$. For randomized linear sketch complexity, which is denoted by $R^\text{lin}(f)$, the $k$ sets are chosen in advance from a joint distribution and are available for recovering $f(x)$. Please see the paper by Kannan, Mossel, Sanyal and Yaroslavtsev {{cite|KannanMSY-18}} for more details. |
Given $f$, we also define $f^+:\{0,1\}^n\times \{0,1\}^n \rightarrow\{0,1\}$ as $f^+ (x,y) = f(x\oplus y)$ for all $x,y\in\{0,1\}^n$, where $\oplus$ denotes bitwise XOR. It is known that $D^\text{lin}(f) = D^\rightarrow(f^+)$ {{cite|MontanaroO-09}}, where $D^\rightarrow$ denotes one-way communication complexity (Alice sends one message to Bob). | Given $f$, we also define $f^+:\{0,1\}^n\times \{0,1\}^n \rightarrow\{0,1\}$ as $f^+ (x,y) = f(x\oplus y)$ for all $x,y\in\{0,1\}^n$, where $\oplus$ denotes bitwise XOR. It is known that $D^\text{lin}(f) = D^\rightarrow(f^+)$ {{cite|MontanaroO-09}}, where $D^\rightarrow$ denotes one-way communication complexity (Alice sends one message to Bob). | ||
Prove (or disprove) the following conjecture: $R^\text{lin}(f) = \tilde{\Theta}(R^\rightarrow(f^+))$. | Prove (or disprove) the following conjecture: $R^\text{lin}(f) = \tilde{\Theta}(R^\rightarrow(f^+))$. | ||
Latest revision as of 21:50, 12 April 2018
| Suggested by | Grigory Yaroslavtsev |
|---|---|
| Source | Banff 2017 |
| Short link | https://sublinear.info/78 |
For a function $f:\{0,1\}^n\rightarrow\{0,1\}$, we define its deterministic linear sketch complexity $D^\text{lin}(f)$ as a the smallest number $k$ such that there exist $k$ sets $S_1,\ldots,S_k \subseteq [n]$ such that for any $x\in \{0,1\}^n$, we can compute $f(x)$ using $\sum_{i\in S_1} x_i, \ldots, \sum_{i\in S_k} x_i$, where the sum is mod $2$. For randomized linear sketch complexity, which is denoted by $R^\text{lin}(f)$, the $k$ sets are chosen in advance from a joint distribution and are available for recovering $f(x)$. Please see the paper by Kannan, Mossel, Sanyal and Yaroslavtsev [KannanMSY-18] for more details.
Given $f$, we also define $f^+:\{0,1\}^n\times \{0,1\}^n \rightarrow\{0,1\}$ as $f^+ (x,y) = f(x\oplus y)$ for all $x,y\in\{0,1\}^n$, where $\oplus$ denotes bitwise XOR. It is known that $D^\text{lin}(f) = D^\rightarrow(f^+)$ [MontanaroO-09], where $D^\rightarrow$ denotes one-way communication complexity (Alice sends one message to Bob).
Prove (or disprove) the following conjecture: $R^\text{lin}(f) = \tilde{\Theta}(R^\rightarrow(f^+))$.
