DIMACS Theoretical Computer Science Seminar

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


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