Open Problems:78 - Revision history

12.39.6.101: added Sanyal

2018-04-12T21:50:44Z

added Sanyal

12.39.6.101: reference

2018-04-12T21:50:19Z

reference

Krzysztof Onak at 03:06, 28 April 2017

2017-04-28T03:06:53Z

Blackc4 at 04:03, 2 April 2017

2017-04-02T04:03:41Z

Blackc4 at 22:38, 1 April 2017

2017-04-01T22:38:27Z

Blackc4 at 22:18, 1 April 2017

2017-04-01T22:18:53Z

Blackc4: Created page with "{{Header |source=banff17 |who=Grigory Yaroslavtsev }} "

2017-03-31T20:20:23Z

Created page with "{{Header |source=banff17 |who=Grigory Yaroslavtsev }} <references />"

New page

{{Header
|source=banff17
|who=Grigory Yaroslavtsev
}}

<references />

@@ Line 3: / Line 3: @@
 |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).
 Prove (or disprove) the following conjecture: $R^\text{lin}(f) = \tilde{\Theta}(R^\rightarrow(f^+))$.

@@ Line 3: / Line 3: @@
 |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|KannanMY-16}} 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, 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).
 Prove (or disprove) the following conjecture: $R^\text{lin}(f) = \tilde{\Theta}(R^\rightarrow(f^+))$.

@@ Line 3: / Line 3: @@
 |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]$, and 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 Kannan, Mossel, and Yaroslavtsev {{cite|KannanMY-16}}
+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^+))$.

@@ 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)$.
+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 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 Kannan, Mossel, and Yaroslavtsev {{cite|KannanMY-16}}
 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|MontanaroO-09}}, where $D^\rightarrow$ denotes one-way communication complexity (Alice sends one message to Bob).

@@ Line 6: / Line 6: @@
 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).
+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|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^+))$.
 <references />

← Older revision		Revision as of 22:18, 1 April 2017
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 />