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.
2. a 9. 12. 2009 (středa [Wednesday], 14:30, MÚ Žitná 25, seminární místnost v přízemí zadní budovy)
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:
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
Nati Linial, Yishay Mansour and Noam Nisan:
Constant-depth circuits, Fourier transform and learnability
Mark Braverman:
Poly-logarithmic independence fools AC0 circuits
Vince Grolmusz:
Superpolynomial Size Set-Systems with Restricted Intersections mod 6 and Explicit Ramsey Graphs