Oznámení o seminářích se distribuuje pomocí mailing listu, do
kterého se
můžete zapsat na adrese
http://list.math.cas.cz/listinfo/complexity-seminar.
27. 10. 2010 (středa [Wednesday], 14:30, MÚ Žitná 25, seminární místnost v přízemí zadní budovy)
R.A. Moser, A constructive proof of Lovasz Local Lemma
(referuje Pavel Pudlák)
Abstract: This is a nice new (2008) and constructive proof of the useful lemma.
20. 10. 2010 (středa [Wednesday], 14:30, MÚ Žitná 25)
Kristoffer Arnsfelt Hansen (Aarhus University): Exact threshold functions and Boolean circuits
Abstract: In this talk we will cover exact threshold functions from a number of perspectives. First a brief survey of research on constant depth threshold circuits is given followed by a detailed introduction of exact threshold functions and corresponding pure circuit classes they give rise to. Relationships between threshold circuits and exact threshold counterparts are covered. A major open problem in Boolean circuit complexity is to provide an explicit super-polynomial lower bound for depth two threshold circuits. We identify the class of depth two exact threshold circuits as a natural subclass of these where also no explicit lower bounds are known.
Next exact threshold functions are studied as models of representing Boolean functions, specifically by linear equations and in general degree d polynomials. We give upper and lower bounds on the maximum magnitude (absolute value) of the coefficients required to represent such functions. These bounds are very close and in the linear case in particular they are almost matching. In the process we construct new families of ill-conditioned matrices
Finally is given a short overview of other uses of exact threshold functions in Boolean circuit complexity.
The talk is based on joint work Laci Babai, Vladimir Podolskii and Xiaoming Sun.
