Room 327

Linear sketching and one-way communication

Swagato Sanyal

TIFR / NUS

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 elementary information theory.