BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/892
DTSTAMP:20230914T125942Z
SUMMARY:On the Weakness of Linear Decision Lists
DESCRIPTION:Speaker: Nikhil S Mande\n\nAbstract: \nAbstract: \nWe consider
functions computable efficiently by "linear decision lists"\, which are d
ecision lists where the queries are linear threshold functions.\nWe observ
e that an argument of Turan and Vatan shows that functions efficiently com
putable by linear decision lists must have large monochromatic rectangles.
We then use this fact to prove an exponential lower bound for the size
of any linear decision list computing MAJ o XOR\, completely resolving an
open question posed by Turan and Vatan.\nNo background will be assumed.\nB
ased on joint work with Arkadev Chattopadhyay\, Meena Mahajan and Nitin Sa
urabh\n
URL:https://www.tcs.tifr.res.in/web/events/892
DTSTART;TZID=Asia/Kolkata:20180720T171500
DTEND;TZID=Asia/Kolkata:20180720T181500
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR