Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR09-048 | 29th May 2009 00:00

#### On the Complexity of Boolean Functions in Different Characteristics

TR09-048
Authors: Parikshit Gopalan, Shachar Lovett, Amir Shpilka
Publication: 1st June 2009 09:49
Keywords:

Abstract:

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

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

ISSN 1433-8092 | Imprint