A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length

作者：Podolskii V V^*; Sherstov A A

来源：Mathematical Notes, 2010, 87(5-6): 860-873.

DOI：10.1134/S0001434610050263

• Boolean function
• integer-valued polynomial
• sign function
• perceptron
• Boolean circuit
• complexity theory
• discrete Fourier transform
• exponential gap

A Boolean function f: {-1, +1} (n) -> {-1, +1} is called the sign function of an integer-valued polynomial p(x) if f(x) = sgn(p(x)) for all x a {-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, ..., n - 1, we explicitly construct a function f: {-1, +1} (n) -> {-1, +1} that requires a weight of the form exp{I similar to(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{I similar to(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.

• 出版日期2010-6