Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #5 to TR16-174 | 7th September 2017 04:06

#### Linear Sketching over $\mathbb F_2$

Revision #5
Authors: Elchanan Mossel, Sampath Sampath Kannan, Swagato Sanyal, Grigory Yaroslavtsev
Accepted on: 7th September 2017 04:06
Keywords:

Abstract:

We initiate a systematic study of linear sketching over $\mathbb F_2$. For a given Boolean function $f \colon \{0,1\}^n \to \{0,1\}$ a randomized $\mathbb F_2$-sketch is a distribution $\mathcal M$ over $d \times n$ matrices with elements over $\mathbb F_2$ such that $\mathcal Mx$ suffices for computing $f(x)$ with high probability. We study a connection between $\mathbb F_2$-sketching and a two-player one-way communication game for the corresponding XOR-function. Our results show that this communication game characterizes $\mathbb F_2$-sketching under the uniform distribution (up to dependence on error). Implications of this result include: 1) a composition theorem for $\mathbb F_2$-sketching complexity of a recursive majority function, 2) a tight relationship between $\mathbb F_2$-sketching complexity and Fourier sparsity, 3) lower bounds for a certain subclass of symmetric functions. We also fully resolve a conjecture of Montanaro and Osborne regarding one-way communication complexity of linear threshold functions by designing an $\mathbb F_2$-sketch of optimal size.

Furthermore, we show that (non-uniform) streaming algorithms that have to process random updates over $\mathbb F_2$ can be constructed as $\mathbb F_2$-sketches for the uniform distribution with only a minor loss. In contrast with the previous work of Li, Nguyen and Woodruff (STOC'14) who show an analogous result for linear sketches over integers in the adversarial setting our result doesn't require the stream length to be triply exponential in $n$ and holds for streams of length $\tilde O(n)$ constructed through uniformly random updates. Finally, we state a conjecture that asks whether optimal one-way communication protocols for XOR-functions can be constructed as $\mathbb F_2$-sketches with only a small loss.

Revision #4 to TR16-174 | 11th November 2016 16:14

#### Linear Sketching over $\mathbb F_2$

Revision #4
Authors: Elchanan Mossel, Sampath Sampath Kannan, Grigory Yaroslavtsev
Accepted on: 11th November 2016 16:14
Keywords:

Abstract:

We initiate a systematic study of linear sketching over $\mathbb F_2$. For a given Boolean function $f \colon \{0,1\}^n \to \{0,1\}$ a randomized $\mathbb F_2$-sketch is a distribution $\mathcal M$ over $d \times n$ matrices with elements over $\mathbb F_2$ such that $\mathcal Mx$ suffices for computing $f(x)$ with high probability. We study a connection between $\mathbb F_2$-sketching and a two-player one-way communication game for the corresponding XOR-function. Our results show that this communication game characterizes $\mathbb F_2$-sketching under the uniform distribution (up to dependence on error). Implications of this result include: 1) a composition theorem for $\mathbb F_2$-sketching complexity of a recursive majority function, 2) a tight relationship between $\mathbb F_2$-sketching complexity and Fourier sparsity, 3) lower bounds for a certain subclass of symmetric functions. We also fully resolve a conjecture of Montanaro and Osborne regarding one-way communication complexity of linear threshold functions by designing an $\mathbb F_2$-sketch of optimal size.

Furthermore, we show that (non-uniform) streaming algorithms that have to process random updates over $\mathbb F_2$ can be constructed as $\mathbb F_2$-sketches for the uniform distribution with only a minor loss. In contrast with the previous work of Li, Nguyen and Woodruff (STOC'14) who show an analogous result for linear sketches over integers in the adversarial setting our result doesn't require the stream length to be triply exponential in $n$ and holds for streams of length $\tilde O(n)$ constructed through uniformly random updates. Finally, we state a conjecture that asks whether optimal one-way communication protocols for XOR-functions can be constructed as $\mathbb F_2$-sketches with only a small loss.

Changes to previous version:

Revision #3 to TR16-174 | 7th November 2016 05:51

#### Linear Sketching over $\mathbb F_2$

Revision #3
Authors: Elchanan Mossel, Sampath Sampath Kannan, Grigory Yaroslavtsev
Accepted on: 7th November 2016 05:51
Keywords:

Abstract:

We initiate a systematic study of linear sketching over $\mathbb F_2$. For a given Boolean function $f \colon \{0,1\}^n \to \{0,1\}$ a randomized $\mathbb F_2$-sketch is a distribution $\mathcal M$ over $d \times n$ matrices with elements over $\mathbb F_2$ such that $\mathcal Mx$ suffices for computing $f(x)$ with high probability. We study a connection between $\mathbb F_2$-sketching and a two-player one-way communication game for the corresponding XOR-function. Our results show that this communication game characterizes $\mathbb F_2$-sketching under the uniform distribution (up to dependence on error). Implications of this result include: 1) a composition theorem for $\mathbb F_2$-sketching complexity of a recursive majority function, 2) a tight relationship between $\mathbb F_2$-sketching complexity and Fourier sparsity, 3) lower bounds for a certain subclass of symmetric functions. We also fully resolve a conjecture of Montanaro and Osborne regarding one-way communication complexity of linear threshold functions by designing an $\mathbb F_2$-sketch of optimal size.

Furthermore, we show that (non-uniform) streaming algorithms that have to process random updates over $\mathbb F_2$ can be constructed as $\mathbb F_2$-sketches for the uniform distribution with only a minor loss. In contrast with the previous work of Li, Nguyen and Woodruff (STOC'14) who show an analogous result for linear sketches over integers in the adversarial setting our result doesn't require the stream length to be triply exponential in $n$ and holds for streams of length $\tilde O(n)$ constructed through uniformly random updates. Finally, we state a conjecture that asks whether optimal one-way communication protocols for XOR-functions can be constructed as $\mathbb F_2$-sketches with only a small loss.

Revision #2 to TR16-174 | 7th November 2016 05:50

#### Linear Sketching over $\mathbb F_2$

Revision #2
Authors: Elchanan Mossel, Grigory Yaroslavtsev
Accepted on: 7th November 2016 05:50
Keywords:

Abstract:

We initiate a systematic study of linear sketching over $\mathbb F_2$. For a given Boolean function $f \colon \{0,1\}^n \to \{0,1\}$ a randomized $\mathbb F_2$-sketch is a distribution $\mathcal M$ over $d \times n$ matrices with elements over $\mathbb F_2$ such that $\mathcal Mx$ suffices for computing $f(x)$ with high probability. We study a connection between $\mathbb F_2$-sketching and a two-player one-way communication game for the corresponding XOR-function. Our results show that this communication game characterizes $\mathbb F_2$-sketching under the uniform distribution (up to dependence on error). Implications of this result include: 1) a composition theorem for $\mathbb F_2$-sketching complexity of a recursive majority function, 2) a tight relationship between $\mathbb F_2$-sketching complexity and Fourier sparsity, 3) lower bounds for a certain subclass of symmetric functions. We also fully resolve a conjecture of Montanaro and Osborne regarding one-way communication complexity of linear threshold functions by designing an $\mathbb F_2$-sketch of optimal size.

Furthermore, we show that (non-uniform) streaming algorithms that have to process random updates over $\mathbb F_2$ can be constructed as $\mathbb F_2$-sketches for the uniform distribution with only a minor loss. In contrast with the previous work of Li, Nguyen and Woodruff (STOC'14) who show an analogous result for linear sketches over integers in the adversarial setting our result doesn't require the stream length to be triply exponential in $n$ and holds for streams of length $\tilde O(n)$ constructed through uniformly random updates. Finally, we state a conjecture that asks whether optimal one-way communication protocols for XOR-functions can be constructed as $\mathbb F_2$-sketches with only a small loss.

Revision #1 to TR16-174 | 7th November 2016 05:49

#### Linear Sketching over $\mathbb F_2$

Revision #1
Authors: Elchanan Mossel, Sampath Sampath Kannan, Grigory Yaroslavtsev
Accepted on: 7th November 2016 05:49
Keywords:

Abstract:

We initiate a systematic study of linear sketching over $\mathbb F_2$. For a given Boolean function $f \colon \{0,1\}^n \to \{0,1\}$ a randomized $\mathbb F_2$-sketch is a distribution $\mathcal M$ over $d \times n$ matrices with elements over $\mathbb F_2$ such that $\mathcal Mx$ suffices for computing $f(x)$ with high probability. We study a connection between $\mathbb F_2$-sketching and a two-player one-way communication game for the corresponding XOR-function. Our results show that this communication game characterizes $\mathbb F_2$-sketching under the uniform distribution (up to dependence on error). Implications of this result include: 1) a composition theorem for $\mathbb F_2$-sketching complexity of a recursive majority function, 2) a tight relationship between $\mathbb F_2$-sketching complexity and Fourier sparsity, 3) lower bounds for a certain subclass of symmetric functions. We also fully resolve a conjecture of Montanaro and Osborne regarding one-way communication complexity of linear threshold functions by designing an $\mathbb F_2$-sketch of optimal size.

Furthermore, we show that (non-uniform) streaming algorithms that have to process random updates over $\mathbb F_2$ can be constructed as $\mathbb F_2$-sketches for the uniform distribution with only a minor loss. In contrast with the previous work of Li, Nguyen and Woodruff (STOC'14) who show an analogous result for linear sketches over integers in the adversarial setting our result doesn't require the stream length to be triply exponential in $n$ and holds for streams of length $\tilde O(n)$ constructed through uniformly random updates. Finally, we state a conjecture that asks whether optimal one-way communication protocols for XOR-functions can be constructed as $\mathbb F_2$-sketches with only a small loss.

### Paper:

TR16-174 | 7th November 2016 05:01

#### Linear Sketching over $\mathbb F_2$

TR16-174
Authors: Elchanan Mossel, Sampath Sampath Kannan, Grigory Yaroslavtsev
Publication: 7th November 2016 05:15
Keywords:

Abstract:

We initiate a systematic study of linear sketching over $\mathbb F_2$. For a given Boolean function $f \colon \{0,1\}^n \to \{0,1\}$ a randomized $\mathbb F_2$-sketch is a distribution $\mathcal M$ over $d \times n$ matrices with elements over $\mathbb F_2$ such that $\mathcal Mx$ suffices for computing $f(x)$ with high probability. We study a connection between $\mathbb F_2$-sketching and a two-player one-way communication game for the corresponding XOR-function. Our results show that this communication game characterizes $\mathbb F_2$-sketching under the uniform distribution (up to dependence on error). Implications of this result include: 1) a composition theorem for $\mathbb F_2$-sketching complexity of a recursive majority function, 2) a tight relationship between $\mathbb F_2$-sketching complexity and Fourier sparsity, 3) lower bounds for a certain subclass of symmetric functions. We also fully resolve a conjecture of Montanaro and Osborne regarding one-way communication complexity of linear threshold functions by designing an $\mathbb F_2$-sketch of optimal size.

Furthermore, we show that (non-uniform) streaming algorithms that have to process random updates over $\mathbb F_2$ can be constructed as $\mathbb F_2$-sketches for the uniform distribution with only a minor loss. In contrast with the previous work of Li, Nguyen and Woodruff (STOC'14) who show an analogous result for linear sketches over integers in the adversarial setting our result doesn't require the stream length to be triply exponential in $n$ and holds for streams of length $\tilde O(n)$ constructed through uniformly random updates. Finally, we state a conjecture that asks whether optimal one-way communication protocols for XOR-functions can be constructed as $\mathbb F_2$-sketches with only a small loss.

### Comment(s):

Comment #1 to TR16-174 | 25th November 2016 09:26

#### One-way Communication and Linear Sketch for Uniform Distribution

Comment #1
Authors: Swagato Sanyal
Accepted on: 25th November 2016 09:26
Keywords:

Abstract:

This note is prepared based on the article titled \textquotedblleft Linear Sketching over $\mathbb{F}_2$\textquotedblright (ECCC TR16-174) by Sampath Kannan, Elchanan Mossel and Grigory Yaroslavtsev. We quantitatively improve the parameters of Theorem 1.4 of the above work. In particular, our result implies that the one-way communication complexity of any function $f^+(x,y):=f(x \oplus y)$ corresponding to the uniform distribution over the input domain $\{+1,-1\}^n \times \{+1,-1\}^n$ and error $\frac{1}{18}$ is asymptotically lower bounded by the linear sketch compexity of $f(x)$ corresponding to the uniform distribution over the input domain $\{+1,-1\}^n$ and error $\frac{1}{3}$. Our proof is information theoretic; our improvement is obtained by studying the mutual information between Alice's message and the evaluation of certain parities in the Fourier support of $f$ on her input.

Comment #2 to TR16-174 | 1st December 2016 09:42

#### One-way Communication and Linear Sketching for Uniform Distribution

Comment #2
Authors: Swagato Sanyal
Accepted on: 1st December 2016 09:42
This note is prepared based on the article titled \textquotedblleft Linear Sketching over $\mathbb{F}_2$\textquotedblright (ECCC TR16-174) by Sampath Kannan, Elchanan Mossel and Grigory Yaroslavtsev. We quantitatively improve the parameters of Theorem 1.4 of the above work, as well as an earlier bound of ours. In particular, our result implies that for every $\epsilon \in (0,\frac{1}{2})$ and every constant $\delta>0$, the one-way communication complexity of any Boolean function $f^+(x,y):=f(x \oplus y)$ corresponding to the uniform distribution over the input domain $\{+1,-1\}^n \times \{+1,-1\}^n$ and error $\epsilon$, is asymptotically lower bounded by the linear sketch complexity of $f(x)$ corresponding to the uniform distribution over the input domain $\{+1,-1\}^n$ and error $(2+\delta)\epsilon$. Our proof is information theoretic; our improvement is obtained by studying the mutual information between Alice's message and the evaluation of certain parities in the Fourier support of $f$ on her input.