Vybrané kapitoly z výpočetní
složitosti I
Michal Koucký
<koucky@math.cas.cz>
ZS 2006/2007
TIN085 - 2/1 Z, Zk
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ů).
- Kryptografické pseudonáhodné generátory (Rabinova funkce, hybridní argument, Goldreich-Levinův predikát, XOR lemma).
- Pseudonáhodné funkce, přirozené důkazy (natural proofs).
- Pseudonáhodné generátory pro časově omezené výpočty (hardness vs randomness, Nisan-Wigdersonův pseudonáhodný generátor, příklady užití, worst-case/avg-case, uniformní předpoklady, optimální konstrukce, hitting sets).
- Extraktory náhodnosti (Trevisanův extraktor, Kamp-Zuckermanův extraktor).
Domácí úkoly