BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/741
DTSTAMP:20230914T125936Z
SUMMARY:Linear Sketching and One-way Communication
DESCRIPTION:Speaker: Swagato Sanyal (School of Technology and Computer Scie
nce\nTata Institute of Fundamental Research\nHomi Bhabha Road\nNavy Nagar\
nMumbai 400005)\n\nAbstract: \nLinear sketch complexity of a Boolean funct
ion f on a set of n inputs\, introduced by Kannan\, Mossel and Yaroslavtse
v\, is\, in informal terms\, the smallest integer d such that the value of
the function can be concluded with high probability from the evaluation o
f 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 o
ne-way communication complexity of the function F(x\,y):=f(x+y) ('+' denot
es the bit-wise xor of two strings here). This is because given a cheap li
near sketching\, the players of the communication game can easily simulate
it with communication comparable to the cost of the sketch. The authors o
f the above-mentioned work conjectured that linear sketch complexity is al
so a lower-bound on the complexity of this communication problem. In other
words\, linear sketch complexity characterizes the complexity of the comm
unication problem. The motivation of this conjecture comes from the observ
ation that all known communication protocols are obtained from some underl
ying linear sketching. The authors proved a similar statement when the inp
uts are sampled from uniform distribution. We improve on the parameters of
their result in this work. Our proof uses Fourier analysis of Boolean fun
ctions and information theory.\n
URL:https://www.tcs.tifr.res.in/web/events/741
DTSTART;TZID=Asia/Kolkata:20170106T160000
DTEND;TZID=Asia/Kolkata:20170106T173000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR