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.
Poslední úprava: T_KTI (12.05.2006)
This course covers advanced topics in computational complexity. Each semester will be devoted to a different topic. Topics will include among others: randomness and pseudorandom generators, communication complexity and interactive protocols, error-correcting codes and their applications in complexity, lower bounds, expanders and their applications. The course is intended to students from upper classes and to graduate students. Prerequisites: understanding of elementary concepts from computational complexity, probability theory and discrete math.
Poslední úprava: T_KTI (12.05.2006)
Cíl předmětu
Naučit vybrané kapitoly z výpočetní složitosti
Poslední úprava: T_KTI (23.05.2008)
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í.
Poslední úprava: T_KTI (12.05.2006)
Randomness and pseudorandom generators.
Communication complexity and interactive protocols.
Error-correcting codes and their applications in complexity.
