BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/618
DTSTAMP:20230914T125931Z
SUMMARY:Polynomial Approximations Over $\\mathbb{Z}/{p^k}\\mathbb{Z}$
DESCRIPTION:Speaker: Abhishek Bhrushundi (Rutgers University\nDepartment of
Computer Science\nNew Jersey\nUnited States of America\n )\n\nAbstract:
\nAbstract: It is known from the works of Lovett et al.\, Tao and Ziegler\
, and more recently\, Bhowmick and Lovett\, that there are Boolean functio
ns which do not correlate well with classical polynomials of a certain deg
ree but have good correlation with some non-classical polynomial of the sa
me degree.\n\nNoting that the notion of approximation is different from th
at of correlation in the case of non-classical polynomials\, Bhowmick and
Lovett asked the following questions:\n \n\nDo non-classical polynomials
of degree $o(\\sqrt{n})$ approximate the majority function better than cla
ssical polynomials of the same degree?\nIs there any Boolean function for
which non-classical polynomials offer an advantage over classical polynomi
als in the case of approximation?\n\nWe give a negative answer to the firs
t question. We do so by studying polynomials over rings of the form $\\mat
hbb{Z}/{p^k}\\mathbb{Z}$ and observing that non-classical polynomial are a
special case of such polynomials. Our proof essentially involves proving
tight bounds for \\textit{weak representations} of the majority function o
ver $\\mathbb{Z}/{p^k}\\mathbb{Z}$\, strengthening classical results of Sz
egedy and Smolensky.\n\nFor the second question\, we give a positive answe
r by showing that elementary symmetric polynomials of a suitable degree ar
e well approximated by non-classical polynomials (this is joint work with
Prahladh Harsha and Srikanth Srinivasan).\n \n
URL:https://www.tcs.tifr.res.in/web/events/618
DTSTART;TZID=Asia/Kolkata:20150818T160000
DTEND;TZID=Asia/Kolkata:20150818T170000
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR