Cas konání: Ut 10:40-12:10.
Místo konání: Malá Strana - S9.
Obsahem této přednášky jsou pokročilé partie z výpočetní složitosti. Tento semestr bude věnován náhodnosti a konstrukci pseudonáhodných generátorů. Přednáška je určena především studentům vyšších ročníků studia a doktorandům. Přednáška předpokládá základní znalosti z výpočetní složitosti, pravděpodobnosti a diskrétní matematiky.
Plán přednášky
Zopakování základních pojmů (pravděpodobnost, konečná tělesa a polynomy, výpočetní modely a třídy složitosti).
Příklady pravděpodobnostních algoritmů.
Třídy RP, BPP, co-RP, RL, co-RL.
Zmenšování chyby, BPP ⊆ P/poly, BPP ⊆ NPNP.
Pseudonáhodné generátory pro prostorově omezené výpočty (Nisanův pseudonáhodný generátor, příklady použití, RL ⊆ TISP(poly, log2 n), Reingoldův algoritmus pro testování souvislosti neorientovaných grafů).