Semináø z výpoèetní slo¾itosti

Michal Koucký, Pavel Pudlák

Doba a místo konání

Èas: ètvrtek 14:00-15:30. Místo konání semináøe: MÚ ®itná 25, seminární místnost na sekretariátì 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]

Tento semestr se budeme vìnovat star¹ím a novým výsledkùm ohlednì disperserù, extractorù, expanderù, Ajtai-Kolmos-Szemeredi tøídících sítí a pseudonáhodných generátorù.

19. 5. 2011 (ètvrtek [Thursday], 14:00, MÚ ®itná 25, seminární místnost v na sekretariátì v zadní budovì)

Russell Impagliazzo: Relativized Separations of Worst-Case and Average-Case Complexities for NP

Abstract: Non-relativization of complexity issues can be interpreted as giving evidence that these issues cannot be resolved by "black-box" techniques. We show that the assumption \$DistNP \subseteq AvgP\$ does not imply that \$NP\subseteq BPP\$ by relativizing techniques. More precisely, we give an oracle relative to which the assumption holds but the conclusion fails. Moreover, relative to our oracle, \$NP \cap co-NP\$ requires exponential sized circuits. We also show that average-case easiness for \$NP\$ does not imply average-case easiness for the polynomial hierarchy. Video lecture.

Pøedchozí program semináøe

12. 5. 2011 (ètvrtek [Thursday], 14:00, MÚ ®itná 25, seminární místnost v na sekretariátì v zadní budovì)

Pavel Hrube¹: The sum-of-squares problem over integers

Abstract: I will show that if  (x1^2+..+ xk^2)(y1^2+..+yk^2) = z1^2+..+zn^2, where z1,.., zn are polynomials with integer coefficients, then n is at least \Omega(k^{1.25}).

5. 5. 2011 (ètvrtek [Thursday], 14:00, MÚ ®itná 25)

Pavel Hrube¹: Non-commutative arithmetic circuits and the sum-of-squares problem

Abstract: Arithmetic circuit is a basic model for computing polynomials over a field. In a non-commutative polynomial, variables do not multiplicatively commute; one can think of the variables as representing matrices. They are computed by non-commutative arithmetic circuits. The major open question is to prove a superpolynomial lower bound on the size of a circuit computing an explicit non-commutative polynomial. This question is related to a classical mathematical problem, the so called sum-of-squares problem. This lies on the boundary of algebra and topology, and is interesting from a purely mathematical point of view. Joint work with Amir Yehudayoff and Avi Wigderson.

21. 4. 2011 (ètvrtek [Thursday], 14:00, MÚ ®itná 25)

Jan Bulánek: Online labeling problem

Abstract: I will present a new lower bound for the number of reassignments for the online labeling problem. The online labeling problem is a task where the input is a stream of N items with defined linear ordering and you have to assign one of cN (c>1) integer labels to each item so that the ordering of labels will respect the ordering of items. However, since you don't know the stream in advance, sometimes it could be necessary to reassign some of already assigned labels. The goal is to make as few reassignments as possible.

Joint work with Michal Koucký.

7. and 14. 4. 2011 (ètvrtek [Thursday], 14:00, MÚ ®itná 25)

Emil Jeøábek: Sorting networks

Abstract: I will present the construction of sorting networks of the asymptotically optimal depth O(log n) by Ajtai, Komlós and Szemerédi, in the version given by Paterson [Improved sorting networks with O(log N) depth, Algorithmica 5 (1990), 75--92].

30. 3. 2011 (støeda [Wednesday], 14:30, MÚ ®itná 25)

Pavel Pudlák: Lower bounds on tensor rank

Abstract: I will present some lower bounds from the paper of Alexeev, Forbes, Tsimerman (ECCC TR 10 2011) and more. Rank of order 3 tensors is used to estimate multiplicative complexity of bilinear transformations, such as matrix multiplication. The renewed in this topic is due to Raz's result that large lower bounds on tensor rank of order n tensors can be used for general algebraic circuits.

16. 3. 2011 (støeda [Wednesday], 14:30, MÚ ®itná 25)

We will start our seminar with:

Pavel Pudlák: Computing Error Correcting Codes in Bounded Depth - Lower bound for depth 2

Abstract: This is a part of the paper in preparation whose authors are Gál, Hansen, Koucký, Pudlák, and Viola. It will be presented by me.