Difference between revisions of "Open Problems:78"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
(Created page with "{{Header |source=banff17 |who=Grigory Yaroslavtsev }} <references />")
 
Line 4: Line 4:
 
}}
 
}}
  
 +
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]$ and for any $x\in \{0,1\}^n$ we can determine $f(x)$ using $\sum_{i\in S_1} x_i, \ldots, \sum_{i\in S_k} x_i$, where the sum is mod $2$.  Randomized linear sketch complexity is denoted by $R^\text{lin}(f)$.
  
 +
Given $f$, we also define $f^+:\{0,1\}^n\times \{0,1\}^n \rightarrow\{0,1\}$ as follows.  For any $x,y\in\{0,1\}^n$, define $f^+ (x,y) = f(x\oplus y)$, where $\oplus$ denotes bitwise XOR.  It is known that $D^\text{lin}(f) = D^\rightarrow(f^+)$ {{cite|Montanaro-O-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^+))$.
  
 
<references />
 
<references />

Revision as of 22:18, 1 April 2017

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]$ and for any $x\in \{0,1\}^n$ we can determine $f(x)$ using $\sum_{i\in S_1} x_i, \ldots, \sum_{i\in S_k} x_i$, where the sum is mod $2$. Randomized linear sketch complexity is denoted by $R^\text{lin}(f)$.

Given $f$, we also define $f^+:\{0,1\}^n\times \{0,1\}^n \rightarrow\{0,1\}$ as follows. For any $x,y\in\{0,1\}^n$, define $f^+ (x,y) = f(x\oplus y)$, where $\oplus$ denotes bitwise XOR. It is known that $D^\text{lin}(f) = D^\rightarrow(f^+)$ [Montanaro-O-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^+))$.