BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/795
DTSTAMP:20230914T125938Z
SUMMARY:A Lower Bound for Perceptrons that Compute Some Separation Problem
DESCRIPTION:Speaker: Suhail Sherif\n\nAbstract: \nWe look at the boolean fu
nction in which the input is a boolean matrix with the promise that either
2/3rd of its rows contain a 1 or 2/3rd of its rows do not contain a 1. Th
e output is 1 if the matrix is of the former kind and 0 if it is of the la
tter kind.\nAs a model of computation\, we look at polynomials with intege
r coefficients which accept an input if the polynomial evaluates to at lea
st 1\, and rejects if the polynomial evaluates to at most 0. (A more rad t
erm for such a model of computation is a 'perceptron') Perceptrons of degr
ee d are closely related to query algorithms with at most d queries.\nWe p
rove that any perceptron computing the function either has large degree (a
t least n^{1/3}) or large coefficients (at least 2^n^{1/4}).\n\nThe proof
I will present is adapted from Nikolai Vereshchagin's original proof of th
e result in his paper "Lower Bounds for Perceptrons Solving some Separatio
n Problems and Oracle Separation of AM from PP". The adaptation is inspire
d by a proof of Thomas Watson in his paper "Quadratic Simulations of Arthu
r-Merlin Games".\n
URL:https://www.tcs.tifr.res.in/web/events/795
DTSTART;TZID=Asia/Kolkata:20170728T171500
DTEND;TZID=Asia/Kolkata:20170728T181500
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR