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

Pavel Pudlák, Jiří Sgall

Předchozí program semináře, letní semestr 2001 [Previous program, Spring 2001]

22. 5. 2001

9.00, MÚ Žitná 25, 1. patro

J. Forster: A Linear Lower Bound on the Unbounded Error Probabilistic Communication Complexity.
(referuje Daniel Kral)

15. 5. 2001

9.00, MÚ Žitná 25, 1. patro

Kirk R. Pruhs (Univ. of Pittsburgh, PA, USA): Multicast Pull Scheduling.

We propose to build middleware that targets the data management issues of multicast dissemination in the current Internet infrastructure. The proposed middleware will make it more amenable for application developers to leverage on existing and upcoming middleware protocols by implementing a set of data management algorithms that is common to several scalable and data-intensive applications. After briefly discussing this middleware, I'll focus on algorithms and algorithmic design techniques for one component, the multicast pull scheduler.

10. 4., 24. 4. 2001

9.00, MÚ Žitná 25, 1. patro

John Watrous: On Quantum and Classical Space-bounded Processes with Algebraic Transition Amplitudes. FOCS 1999: 341-351
(referuje Robert Špalek)

27. 3., 3.4. 2001

9.00, MÚ Žitná 25, 1. patro

R. Raz: Dolní odhady na délku rezolučních důkazů slabého PHP
(referuje Martin Pergel)

Referovaný článek řeší známý problém z oblasti složitosti výrokových kalkulů.

20. 3. 2001

9.00, MÚ Žitná 25, 1. patro

J. Sgall: Silné a slabé delta-systémy

Úvod do této oblasti extremální kombinatoriky množinových systémů.

13.3., 27. 2. 2001

9.00, MÚ Žitná 25, 1. patro

J. Sgall: Rozvrhování s konflikty

Budu referovat článek

The buffer minimization problem for multiprocessor scheduling with conflicts
(spoluautoři: Marek Chrobak, Janos Csirik, Csanad Imreh, John Noga, Gerhard J. Woeginger)

Jde o mírně netradiční model online algoritmů. Technicky zajímavý je nekonstruktivní důkaz existence algoritmu s jistými vlastnostmi za pomoci lineárního programování.

15. 2. 2001

10.00, MÚ Žitná 25, 1. patro

S. Žák: Branching programy - restrikce a dolní meze netradičně.

Zavedeme novy zpusob restringovani branching programu a novy zpusob dokazovani dolnich mezi slozitosti, oboji zalozeno na sledovani dynamiky zpracovani informace v prubehu vypoctu. Definujeme restrikci, ktera je podstatne sirsi nez tzv. read-once branching programy, a dokazujeme pro ni exponencialni dolni mez.