This article is cited in
1 paper
Degree-uniform lower bound on the weights of polynomials with given sign function
Vladimir V. Podolskii Steklov Mathematical Institute, Russian Academy of Sciences, Moscow, Russia
Abstract:
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\}$.
UDC:
510.52 Received in October 2010