|
This article is cited in 2 scientific papers (total in 2 papers)
A Small Decrease in the Degree of a Polynomial with a Given Sign Function Can Exponentially Increase Its Weight and Length
V. V. Podolskiia, A. A. Sherstovb a M. V. Lomonosov Moscow State University
b University of Texas in Austin
Abstract:
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.
Keywords:
Boolean function, integer-valued polynomial, sign function, perceptron, Boolean circuit, complexity theory, discrete Fourier transform, exponential gap.
Received: 20.06.2009
Citation:
V. V. Podolskii, A. A. Sherstov, “A Small Decrease in the Degree of a Polynomial with a Given Sign Function Can Exponentially Increase Its Weight and Length”, Mat. Zametki, 87:6 (2010), 885–899; Math. Notes, 87:6 (2010), 860–873
Linking options:
https://www.mathnet.ru/eng/mzm8734https://doi.org/10.4213/mzm8734 https://www.mathnet.ru/eng/mzm/v87/i6/p885
|
Statistics & downloads: |
Abstract page: | 688 | Full-text PDF : | 193 | References: | 50 | First page: | 13 |
|