Seminář z výpočetní složitosti

Michal Koucký, Pavel Pudlák

Doba a místo konání

Středa 14:30-16:00. Místo konání semináře: MÚ Žitná 25, velká posluchárna v zadní budově.

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.

Kontakt

http://www.math.cas.cz/~koucky/, tel. 222 090 771;
pudlak@math.cas.cz, http://www.math.cas.cz/~pudlak/, tel. 222 090 721;
http://kam.mff.cuni.cz/~sgall/, tel. 221 914 293.

Nejbližší program semináře [Next program]

13. 1. 2010 (středa [Wednesday], 14:30, MÚ Žitná 25, seminární místnost v přízemí zadní budovy)

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.

Předchozí program semináře

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}ⁿ -> {0,1} by the sign of an integer polynomial p of degree k. For us, a polynomial p(x) predicts the value of f(x) if, whenever p(x) ≥ 0, f(x) = 1, and whenever p(x) < 0, f(x) = 0. A low-degree polynomial p is a good approximator for f if it predicts f at almost all points. Given a positive integer k, and a Boolean function f, we ask, ``how good is the best degree k approximation to f?'' We introduce a new lower bound technique which applies to any Boolean function. We show that the lower bound technique yields tight bounds in the case f is parity. Minsky and Papert proved that a perceptron can not compute parity; our bounds indicate exactly how well a perceptron can approximate it. As a consequence, we are able to give the first correct proof that, for a random oracle A, PP^A is properly contained in PSPACE^A. We are also able to prove the old AC⁰ exponential-size lower bounds in a new way. This allows us to prove the new result that an AC⁰ circuit with one majority gate cannot approximate parity. Our proof depends only on basic properties of integer polynomials.

Další plán:

Vince Grolmusz: Superpolynomial Size Set-Systems with Restricted Intersections mod 6 and Explicit Ramsey Graphs