Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR09-048 | 29th May 2009 00:00

On the Complexity of Boolean Functions in Different Characteristics


Authors: Parikshit Gopalan, Shachar Lovett, Amir Shpilka
Publication: 1st June 2009 09:49
Downloads: 3873


Every 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$:

\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$.

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.

ISSN 1433-8092 | Imprint