A Boolean function f on n inputs is called polynomial threshold function if there exists an integer polynomial p on n variables such that for all n-bit strings x it holds that f(x)=1 iff p(x)>0. In this case p is called a perceptron for f. The degree of the perceptron is simply the degree of the polynomial and the weight of the perceptron is the sum of the absolute values of its coefficients.

In this talk we will be interested in the smallest possible weight of a perceptron of a given degree for a given function. We will review upper and lower bounds on this quantity and give some proof ideas.

The talk is based on the following papers:

Vladimir V. Podolskii. Perceptrons of Large Weight. Problems of Information Transmission. 45(1):51-59, 2009.

Vladimir V. Podolskii. A Uniform Lower Bound on Weights of Perceptrons. Proc. of the Third International Computer Science Symposium in Russia (CSR), pp. 261-272, 2008.

V.V. Podolskii, A.A. Sherstov, Reducing by 1 the degree of a polynomial with fixed sign function can increase exponentially its weight and length. Russian Mathematical Surveys, 2009, 64(5), 950-951.