Speaker: |
Abhishek Bhrushundi (Rutgers University Department of Computer Science New Jersey United States of America ) |

Organiser: |
Prahladh Harsha |

Date: |
Tuesday, 18 Aug 2015, 16:00 to 17:00 |

Venue: |
A-212 (STCS Seminar Room) |

(Scan to add to calendar)

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 $o(\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 $\mathbb{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 over $\mathbb{Z}/{p^k}\mathbb{Z}$, 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 (this is joint work with Prahladh Harsha and Srikanth Srinivasan).