CoMA: Bounds on Coefficients of Integer Polynomials with a Given Boolean Sign-function, Vladimir V. Podolskii
2009.11.09 |
| Date | Tue Nov 10 |
| Time | 13:15 — 14:15 |
| Location | Ada-333 |
A Boolean function f on n inputs is called a sign-function of an integer polynomial p on n variables if for all n-bit strings x it holds that p(x)>0 if f(x)=1 and p(x)<0 if f(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 will be 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.
See www.cs.au.dk/~bjarke/compmath/ for details. SK: 5211