ECCC-Report TR16-174https://eccc.weizmann.ac.il/report/2016/174Comments and Revisions published for TR16-174en-usThu, 07 Sep 2017 04:06:59 +0300
Revision 5
| Linear Sketching over $\mathbb F_2$ |
Sampath Sampath Kannan,
Elchanan Mossel,
Swagato Sanyal,
Grigory Yaroslavtsev
https://eccc.weizmann.ac.il/report/2016/174#revision5We 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.
Thu, 07 Sep 2017 04:06:59 +0300https://eccc.weizmann.ac.il/report/2016/174#revision5
Comment 2
| One-way Communication and Linear Sketching for Uniform Distribution |
Swagato Sanyal
https://eccc.weizmann.ac.il/report/2016/174#comment2This 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.Thu, 01 Dec 2016 09:42:08 +0200https://eccc.weizmann.ac.il/report/2016/174#comment2
Comment 1
| One-way Communication and Linear Sketch for Uniform Distribution |
Swagato Sanyal
https://eccc.weizmann.ac.il/report/2016/174#comment1This 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.Fri, 25 Nov 2016 09:26:12 +0200https://eccc.weizmann.ac.il/report/2016/174#comment1
Revision 4
| Linear Sketching over $\mathbb F_2$ |
Sampath Sampath Kannan,
Elchanan Mossel,
Grigory Yaroslavtsev
https://eccc.weizmann.ac.il/report/2016/174#revision4We 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.
Fri, 11 Nov 2016 16:14:58 +0200https://eccc.weizmann.ac.il/report/2016/174#revision4
Revision 3
| Linear Sketching over $\mathbb F_2$ |
Sampath Sampath Kannan,
Elchanan Mossel,
Grigory Yaroslavtsev
https://eccc.weizmann.ac.il/report/2016/174#revision3We 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.
Mon, 07 Nov 2016 05:51:53 +0200https://eccc.weizmann.ac.il/report/2016/174#revision3
Revision 2
| Linear Sketching over $\mathbb F_2$ |
Grigory Yaroslavtsev,
Elchanan Mossel
https://eccc.weizmann.ac.il/report/2016/174#revision2We 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.
Mon, 07 Nov 2016 05:50:30 +0200https://eccc.weizmann.ac.il/report/2016/174#revision2
Revision 1
| Linear Sketching over $\mathbb F_2$ |
Grigory Yaroslavtsev,
Elchanan Mossel,
Sampath Sampath Kannan
https://eccc.weizmann.ac.il/report/2016/174#revision1We 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.
Mon, 07 Nov 2016 05:49:14 +0200https://eccc.weizmann.ac.il/report/2016/174#revision1
Paper TR16-174
| Linear Sketching over $\mathbb F_2$ |
Grigory Yaroslavtsev,
Sampath Sampath Kannan,
Elchanan Mossel
https://eccc.weizmann.ac.il/report/2016/174We 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.
Mon, 07 Nov 2016 05:15:46 +0200https://eccc.weizmann.ac.il/report/2016/174