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

 Pavel Pudlák, Jiří Sgall

J. Forster: A Linear Lower Bound on the Unbounded Error Probabilistic Communication Complexity.
(referuje Daniel Kral) 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.

John Watrous: On Quantum and Classical Space-bounded Processes with Algebraic Transition Amplitudes. FOCS 1999: 341-351
 (referuje Robert Špalek) 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ů.

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

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

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

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.