**27. 10. 2011 **(středa [Wednesday], **14:30,
MÚ Žitná 25**)

**Pavel Pudlák: Extracting computations from propositional proofs.**

**Abstract: **
I will present a new computational model that generalizes
boolean circuits. This model characterizes a certain computational problem
concerning the proof systems that use DNF's (depth 2 Frege systems). The
problem is important mainly for proof complexity, but potentially can
also be used to classify the complexity of combinatorial games. There is
also a new combinatorial game associated with it.

This model was presented by Neil on the logic seminar, but I will say a little more. I will use my slides from the lecture that I gave in Chennai last month.

**1. 12. and 8.12. 2010 **(středa [Wednesday], **14:30,
MÚ Žitná 25**)

**Ryan Williams: Non-Uniform ACC Circuit Lower Bounds**

(referuje Michal Koucký)

**Abstract: **
The class ACC consists of circuit families with constant depth over
unbounded fan-in AND, OR, NOT, and MOD_m gates, where m > 1 is an
arbitrary constant. We prove:

- NTIME(2^n) does not have polynomial size ACC circuits.
- EXP^NP does not have ACC circuits of size 2^{n^o(1)}.

**10. 11. 2010 **(středa [Wednesday], **14:30,
MÚ Žitná 25**)

**Michal Koucký: Computing Error Correcting Codes in Bounded Depth**

**Abstract: **
In this talk I will explain some of the recent work we did with
A. Gál, K. Hansen, P. Pudlák, E. Viola on computing error-correcting codes
by bounded depth circuits.

The work aims to answer the following question: For codes of constant rate and constant relative minimal distance what is the number of wires in constant depth circuits computing the code, i.e., computing the encoding function. We show surprising almost linear bounds.

**27. 10. and 3.11. 2010 **(středa [Wednesday], **14:30,
MÚ Žitná 25**)

** 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.