Vybrané kapitoly z výpočetní složitosti I

Sylabus

- Náhodnost a pseudonáhodné generátory.

- Komunikační složitost a interaktivní protokoly.

- Samoopravné kódy.

- Dolní odhady.

- Expandery a jejich použití.

Upresneni pro rok 2021/22 viz: https://users.math.cas.cz/~talebanfard/mtc.html

Anotace

Obsahem této přednášky jsou pokročilé partie z výpočetní složitosti. Každý semestr bude věnován jinému tématu.

Mezi plánovaná témata patří oblast náhodnosti a pseudonáhodných generátorů, komunikační složitost a interaktivní protokoly, samoopravné kódy a jejich užití ve složitosti, dolní odhady, expandery a jejich použití a další. 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.