| Description |
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:
\begin{itemize}
\item Do non-classical polynomials of degree $o(\sqrt{n})$ approximate the majority function better than classical polynomials of the same degree?
\item Is there any Boolean function for which non-classical polynomials offer an advantage over classical polynomials in the case of approximation?
\end{itemize}
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 $\Ringm{p^k}$, 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).
|