ECCC-Report TR09-048https://eccc.weizmann.ac.il/report/2009/048Comments and Revisions published for TR09-048en-usMon, 01 Jun 2009 09:49:15 +0300
Paper TR09-048
| On the Complexity of Boolean Functions in Different Characteristics |
Parikshit Gopalan,
Shachar Lovett,
Amir Shpilka
https://eccc.weizmann.ac.il/report/2009/048Every Boolean function on $n$ variables can be expressed as a unique multivariate polynomial modulo $p$ for every prime $p$. In this work, we study how the degree of a function in one characteristic affects its complexity in other characteristics. We establish the following general principle: functions with low degree modulo $p$ must have high complexity in every other characteristic $q$.
More precisely, we show the following results about Boolean functions $f:\{0,1\}^n \rightarrow \{0,1\}$ which depend on all $n$ variables, and distinct primes $p,q$:
\begin{itemize}
\item If $f$ has degree $o(\log n)$ modulo $p$, then it must have degree $\Omega(n^{1-o(1)})$ modulo $q$. Thus a Boolean function has degree $o(\log n)$ in only one characteristic. This result is essentially tight as there exist functions that have degree $\log n$ in every characteristic.
\item If $f$ has degree $d = o(\log n)$ modulo $p$, it cannot be computed correctly on more than $ 1- p^{-O(d)}$ fraction of the hypercube by polynomials of degree $n^{\frac{1}{2} - \eps}$ modulo $q$.
\end{itemize}
As a corollary of the above results it follows that if $f$ has degree $o(\log n)$ modulo $p$, then it requires super-polynomial size $\AC_0[q]$ circuits. This gives a lower bound for a broad and natural class of functions.
Mon, 01 Jun 2009 09:49:15 +0300https://eccc.weizmann.ac.il/report/2009/048