BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/719
DTSTAMP:20230914T125935Z
SUMMARY:Unbounded Error Communication Complexity of XOR Functions
DESCRIPTION:Speaker: Nikhil S Mande\n\nAbstract: \nWe consider the unbounde
 d error communication complexity of XOR functions\, i.e. those of the form
  f of XOR\, where f is an arbitrary boolean function on n bits. An interes
 ting conjecture of Zhang and Shi [ZS'09] asserts that for symmetric f\, th
 e unbounded error complexity is essentially characterized by the number of
  points in {0\,...\, n-2} for which D(i) doesn't equal D(i + 2)\, where D 
 is the predicate corresponding to f.\n\nWe make progress on the above conj
 ecture by proving strong lower bounds when f is periodic with period n^{1/
 2 - epsilon} for any constant epsilon > 0. More precisely\, we show that e
 very such XOR function has unbounded error complexity n^{Omega(1)}\, unles
 s f is a constant or parity or its complement\, in which case the complexi
 ty is just O(1). As a direct consequence of this\, we derive new exponenti
 al lower bounds on the size of depth-2 threshold circuits computing such X
 OR functions (this is based on joint work with Arkadev Chattopadhyay).\n
URL:https://www.tcs.tifr.res.in/web/events/719
DTSTART;TZID=Asia/Kolkata:20161021T160000
DTEND;TZID=Asia/Kolkata:20161021T173000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR