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.
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.
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.
