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

**Mark Braverman:
Poly-logarithmic independence fools AC0 circuits**

(referuje Pavel Pudlák)

**Abstract: **
We prove that poly-sized AC0 circuits cannot
distinguish a poly-logarithmically independent distribution
from the uniform one. This settles the 1990 conjecture by
Linial and Nisan (1990). The only prior progress on the
problem was by Bazzi (2007), who showed that O(log^2 n)-
independent distributions fool poly-size DNF formulas.
Razborov (2008) has later given a much simpler proof
for Bazzi's theorem.

**16. 12. 2009 a 5.1.2010 **(středa [Wednesday], **14:30,
MÚ Žitná 25**)

**Nati Linial, Yishay Mansour and Noam Nisan:
Constant-depth circuits, Fourier transform and learnability**

(referuje Iddo Tzameret)

**Abstract: **
Boolean functions in ACO are studied using the harmonic analysis of the cube.
The main result is that an ACO Boolean function has almost all of its power
spectrum on the low-order coefficients. This result implies the following properties
of functions in ACO: functions in ACO have low average sensitivity; they can
be approximated well be a real polynomial of low degree; they cannot be pseudorandom
function generators and their correlation with any polylog-wide independent probability
distribution is small. An O(n^polylog(n))-time algorithm for learning
functions in ACO is obtained. The algorithm observed the behavior of an ACO function
on O(n^polylog(n)) randomly chosen inputs and derives a good approximation for
the Fourier transform of the function. This allows it to predict with high probability the
value of the function on other randomly chosen inputs.

**2. a 9. 12. 2009 **(středa [Wednesday], **14:30,
MÚ Žitná 25**)

**Noam Nisan and Mario Szegedy:
On The Degree of Boolean Functions as Real Polynomials**

(referuje Sebastian Muller)

**Abstract: **
Every boolean function may be represented as a real polynomial. In this
paper we characterize the de gree of this polynomial in terms of certain
combinatorial properties of the boolean function. Our first result is a
tight lower bound of \Omega(log n) on the degree needed to represent any
boolean function that depends on n variables. Our second result states
that for every boolean function f the following measures are all
polynomially related:

- The decision tree complexity of f.
- The degree of the polynomial representing f.
- The smallest degree of a polynomial approximating f in the L_max norm.

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

**Neil Thapen: Hastad's Switching Lemma II**

**Abstract: **
We prove the switching lemma for a different, less uniform, family of random restrictions
that is designed to collapse Sipser functions by at most one
level. This gives an exponential separation between depth k and depth k-1 circuits.

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

**Neil Thapen: Hastad's Switching Lemma**

**Abstract: **
We show that no small constant depth circuit can compute parity, using
Hastad's switching lemma that under a random restriction, with high
probability an OR of small ANDs can be decided by a short decision tree.
We give a simplified proof, based on a combination of Hastad's and
Razborov's proofs.

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

**Russell Impagliazzo (IAS Princeton and UC San Diego, host KA): Algorithmic Dense Model Theorems and Weak Regularity**

**Abstract: **
Green and Tao used a Dense Model Theorem to prove that there are arbitrarily long arithmetic progressions in the primes.
The Dense Model Theorem says, intuitively, that for any class of tests, and any subset of a universe, either there is a
test that ``witnesses'' that the subset is small or a large set indistinguishable from that subset. Reingold, Trevisan,
Tulsiani and Vadhan gave a translation of the original Dense Model Theorem into complexity
theroretic terms, and gave an improved construction (also provided by Gowers).
Here, we show that the Dense Model Theorem follows directly from the
Hardcore Set Theorem (Impagliazzo '95, as improved by Holenstein '05).
Using the boosting based proof of the Hardcore Set Theorem, we obtain
constructive and algorithmic versions. We give general decompostion theorems,
along the lines of Trevisan, Tulsiani, and Vadhan '09. We use a
decompostion theorem to give an improved version of the Weak Graph Regularity Theorem of Frieze and Kannan in the case
of graphs of moderate density (or
pseudo-density.)

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

**Roman Smolensky: Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity**

(referuje Michal Koucký)

**Abstract: **
I will present the argument of Razborov and Smolensky that shows
that bounded depth polynomial size circuits consisting of unbounded fan-in
AND, OR and MOD-q gates cannot compute MOD-p if p and q are distinct
primes.

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

**James Aspnes, Richard Beigel, Merrick Furst, and Steven Rudich:
The Expressive Power of Voting Polynomials**

(referuje Pavel Pudlák)

**Abstract: **We consider the problem of approximating a Boolean function *f* :
{0,1}^{n} -> {0,1}*p* of degree *k*. For us, a polynomial
*p*(* x*) predicts the value of