Kannan, Sampath ;
Mossel, Elchanan ;
Sanyal, Swagato ;
Yaroslavtsev, Grigory
Linear Sketching over F_2
Abstract
We initiate a systematic study of linear sketching over F_2. For a given Boolean function treated as f : F_2^n > F_2 a randomized F_2sketch is a distribution M over d x n matrices with elements over F_2 such that Mx suffices for computing f(x) with high probability. Such sketches for d << n can be used to design smallspace distributed and streaming algorithms.
Motivated by these applications we study a connection between F_2sketching and a twoplayer oneway communication game for the corresponding XORfunction. We conjecture that F_2sketching is optimal for this communication game. Our results confirm this conjecture for multiple important classes of functions: 1) lowdegree F_2polynomials, 2) functions with sparse Fourier spectrum, 3) most symmetric functions, 4) recursive majority function. These results rely on a new structural theorem that shows that F_2sketching is optimal (up to constant factors) for uniformly distributed inputs.
Furthermore, we show that (nonuniform) streaming algorithms that have to process random updates over F_2 can be constructed as F_2sketches for the uniform distribution. 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 does not require the stream length to be triply exponential in n and holds for streams of length O(n) constructed through uniformly random updates.
BibTeX  Entry
@InProceedings{kannan_et_al:LIPIcs:2018:8881,
author = {Sampath Kannan and Elchanan Mossel and Swagato Sanyal and Grigory Yaroslavtsev},
title = {{Linear Sketching over F_2}},
booktitle = {33rd Computational Complexity Conference (CCC 2018)},
pages = {8:18:37},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770699},
ISSN = {18688969},
year = {2018},
volume = {102},
editor = {Rocco A. Servedio},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8881},
URN = {urn:nbn:de:0030drops88819},
doi = {10.4230/LIPIcs.CCC.2018.8},
annote = {Keywords: Linear sketch, Streaming algorithms, XORfunctions, Communication complexity}
}
2018
Keywords: 

Linear sketch, Streaming algorithms, XORfunctions, Communication complexity 
Seminar: 

33rd Computational Complexity Conference (CCC 2018)

Issue date: 

2018 
Date of publication: 

2018 