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