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.