RUS  ENG
Full version
JOURNALS // Trudy Matematicheskogo Instituta imeni V.A. Steklova // Archive

Trudy Mat. Inst. Steklova, 2011 Volume 274, Pages 252–268 (Mi tm3327)

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


 English version:
Proceedings of the Steklov Institute of Mathematics, 2011, 274, 231–246

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025