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