Skip to content Skip to navigation
Seminar
10/21/2015 11:00 am
Core A (Room 301)

Polynomial Approximations over Z/p^kZ

Abhishek Bhrushundi, Rutgers University

Organizer(s): Eric Allender, Michael Saks and Mario Szegedy

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.