Tata Institute of Fundamental Research
Polynomial Approximations Over $\mathbb{Z}/{p^k}\mathbb{Z}$
STCS Seminar
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)
Abstract:
Abstract: It is known from the works of Lovett et al., Tao and Ziegler, and more recently, Bhowmick and 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 $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).
| 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)
Abstract:
Abstract: It is known from the works of Lovett et al., Tao and Ziegler, and more recently, Bhowmick and 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 $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).
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).