Tata Institute of Fundamental Research
Linear Sketching and One-way Communication
STCS Student Seminar
Speaker:
Swagato Sanyal (School of Technology and Computer Science
Tata Institute of Fundamental Research
Homi Bhabha Road
Navy Nagar
Mumbai 400005)
Organiser:
Suhail Sherif
Date:
Friday, 6 Jan 2017, 16:00 to 17:30
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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.
| Speaker: | Swagato Sanyal (School of Technology and Computer Science Tata Institute of Fundamental Research Homi Bhabha Road Navy Nagar Mumbai 400005) |
| Organiser: | Suhail Sherif |
| Date: | Friday, 6 Jan 2017, 16:00 to 17:30 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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.