Degree-uniform lower bound on the weights of polynomials with given sign function

Vladimir V. Podolskii

Informatics and Automation, Algorithmic aspects of algebra and logic, Tome 274 (2011), pp. 252-268

Résumé

A Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ is called the sign function of an integer polynomial $p$ of degree $d$ in $n$ variables if it is true that $f(x)=1$ if and only if $p(x)>0$. In this case the polynomial $p$ is called a threshold gate of degree $d$ for the function $f$. The weight of the threshold gate is the sum of the absolute values of the coefficients of $p$. For any $n$ and $d\le D\le\frac{\varepsilon n^{1/5}}{\log n}$ we construct a function $f$ such that there is a threshold gate of degree $d$ for $f$, but any threshold gate for $f$ of degree at most $D$ has weight $2^{(\delta n)^d/D^{4d}}$, where $\varepsilon>0$ and $\delta>0$ are some constants. In particular, if $D$ is constant, then any threshold gate of degree $D$ for our function has weight $2^{\Omega(n^d)}$. Previously, functions with these properties have been known only for $d=1$ (and arbitrary $D$) and for $D=d$. For constant $d$ our functions are computable by polynomial size DNFs. The best previous lower bound on the weights of threshold gates for such functions was $2^{\Omega(n)}$. Our results can also be translated to the case of functions $f\colon\{-1,1\}^n\to\{-1,1\}$.