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

Michal Koucký
<koucky@math.cas.cz>

LS 2006/2007

TIN086 - 2/1 Z, Zk

Čas konání: bude umluveno na společné úmluvě KAMu.
Místo konání: Malá Strana

Obsahem této přednášky jsou pokročilé partie z výpočetní složitosti. Tento semestr bude věnován komunikační složitosti. Typický problém komunikační složitosti je následující:

Alenka z Aše si chce domluvit po telefonu schůzku s Bobem z Brna. Každý z nich si otevře svůj diář a začnou se dohadovat o vhodném termínu. Otázka je, jak dlouho jim bude trvat, než najdou vhodný termín, tj. kolik informace si musí vyměnit.

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

• Protokoly, komunikační složitost.
• Nedeterministické protokoly.
• Pravděpodobnostní protokoly (soukromé vs. sdílené náhodné bity).
• Přímý součin protokolů.
• Komunikační problém relací.
• Protokoly pro více hráčů.
• Užití (dolní odhady, time-space trade-offs).

Literatura: E. Kushilevitz, N. Nisan, Communication complexity, Cambridge University Press 1997.