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]

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:

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

Předchozí program semináře

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} 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, PPA is properly contained in PSPACEA. We are also able to prove the old AC0 exponential-size lower bounds in a new way. This allows us to prove the new result that an AC0 circuit with one majority gate cannot approximate parity. Our proof depends only on basic properties of integer polynomials.

Další plán:

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


Předchozí program semináře [Past program]