Title: Polynomial Approximations over Z/p^kZ
Speaker: Abhishek Bhrushundi, Rutgers University
Date: Wednesday, October 21, 2015 11:00am-12:00pm
Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
It is known from the works of Lovett-Meshulam-Samrodnitsky, Tao-Ziegler, and more recently, Bhowmick-Lovett, that there are Boolean functions which do not correlate well with classical polynomials of a certain degree but have good correlation with some non-classical polynomial of the same degree.
Noting that the notion of approximation is different from that of correlation in the case of non-classical polynomials, Bhowmick and Lovett asked the following questions:
* Do non-classical polynomials of degree \sqrt{n} approximate the majority function better than classical polynomials of the same degree?
* Is there any Boolean function for which non-classical polynomials offer an advantage over classical polynomials in the case of approximation?
We give a negative answer to the first question. We do so by studying polynomials over rings of the form Z/p^kZ and observing that non-classical polynomial are a special case of such polynomials. Our proof essentially involves proving bounds for "weak representations" of the majority function over Z/p^kZ, strengthening classical results of Szegedy and Smolensky.
For the second question, we give a positive answer by showing that elementary symmetric polynomials of a suitable degree are well approximated by non-classical polynomials.
Joint work with Prahladh Harsha and Srikanth Srinivasan
See: https://dragon.rutgers.edu/~mk1029/theoryseminarF15.html