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