[Colloquium] Talk by Vladimir Podolskii, Steklov Mathematical Institute on June 1, 2010
Katie Casey
caseyk at cs.uchicago.edu
Mon May 17 09:23:58 CDT 2010
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF CHICAGO
Date: Tuesday, June 1, 2010
Time: 3:00 p.m.
Place: Ryerson 251, 1100 E. 58th Street
----------------------------------------------------------
Speaker: Vladimir Podolskii
From: Steklov Mathematical Institute
Title: Bounds on Weights of Perceptrons
Abstract: 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20100517/a0087787/attachment.htm
More information about the Colloquium
mailing list