Paper Info
Title
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 n 2 → F 2 a randomized F 2 -sketch is a distribution M over d × n matrices with elements over F 2 such that Mx suffices for computing f ( x ) with high probability. Such sketches for d L n can be used to design small-space distributed and streaming algorithms. Motivated by these applications we study a connection between F 2 -sketching and a two-player one-way communication game for the corresponding XOR-function. We conjecture that F 2 -sketching is optimal for this communication game. Our results confirm this conjecture for multiple important classes of functions: 1) low-degree F 2 -polynomials, 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 2 -sketching is optimal (up to constant factors) for uniformly distributed inputs. Furthermore, we show that (non-uniform) streaming algorithms that have to process random updates over F 2 can be constructed as F 2 -sketches for the uniform distribution. In contrast with the previous work of Li, Nguyen and Woodruff (STOCu002714) 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.
Year
Venue
Field
2018
CCC
Boolean function,Symmetric function,Discrete mathematics,Streaming algorithm,Matrix (mathematics),Computer science,Uniform distribution (continuous),Communication complexity,Conjecture,Majority function
DocType
Citations 
PageRank 
Conference
0
0.34
References 
Authors
0
4
Name
Order
Citations
PageRank
Sampath Kannan12506275.83
Elchanan Mossel21725145.16
Swagato Sanyal313.39
Grigory Yaroslavtsev420917.36