A Small Decrease in the Degree of a Polynomial with a Given Sign Function Can Exponentially Increase Its Weight and Length

V. V. Podolskii ; A. A. Sherstov

Matematičeskie zametki, Tome 87 (2010) no. 6, pp. 885-899

Résumé

A Boolean function $f\colon\{-1,+1\}^n\to\{-1,+1\}$ is called the sign function of an integer-valued polynomial $p(x)$ if $f(x)=\operatorname{sgn}(p(x))$ for all $x\in\{-1,+1\}^n$. In this case, the polynomial $p(x)$ is called a perceptron for the Boolean function $f$. The weight of a perceptron is the sum of absolute values of the coefficients of $p$. We prove that, for a given function, a small change in the degree of a perceptron can strongly affect the value of the required weight. More precisely, for each $d=1,2,\dots,n-1$, we explicitly construct a function $f\colon\{-1,+1\}^n\to\{-1,+1\}$ that requires a weight of the form $\exp\{\Theta(n)\}$ when it is represented by a degree $d$ perceptron, and that can be represented by a degree $d+1$ perceptron with weight equal to only $O(n^2)$. The lower bound $\exp\{\Theta(n)\}$ for the degree $d$ also holds for the size of the depth 2 Boolean circuit with a majority function at the top and arbitrary gates of input degree $d$ at the bottom. This gap in the weight values is exponentially larger than those that have been previously found. A similar result is proved for the perceptron length, i.e., for the number of monomials contained in it.

Détail

Keywords: Boolean function, integer-valued polynomial, sign function, Boolean circuit, complexity theory, exponential gap.
Mots-clés : perceptron, discrete Fourier transform