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.
21.4. 2011 (čtvrtek [Thursday], 14:00, MÚ Žitná 25, seminární místnost v na sekretariátě v zadní budově)
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 Koucky.
7. and 14.4. 2011 (středa [Wednesday], 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.
