| Description |
Linear sketch complexity of a Boolean function f on a set of n inputs, introduced by Kannan, Mossel and Yaroslavtsev, is, in informal terms, the smallest integer d such that the value of the function can be concluded with high probability from the evaluation of d random F_2-linear functions (or parities) of the input. Linear sketch complexity of a Boolean function f can be easily seen to upper bound the one-way communication complexity of the function F(x,y):=f(x+y) ('+' denotes the bit-wise xor of two strings here). This is because given a cheap linear sketching, the players of the communication game can easily simulate it with communication comparable to the cost of the sketch. The authors of the above-mentioned work conjectured that linear sketch complexity is also a lower-bound on the complexity of this communication problem. In other words, linear sketch complexity characterizes the complexity of the communication problem. The motivation of this conjecture comes from the observation that all known communication protocols are obtained from some underlying linear sketching. The authors proved a similar statement when the inputs are sampled from uniform distribution. We improve on the parameters of their result in this work. Our proof uses Fourier analysis of Boolean functions and information theory.
|