TIN050 - Seminář z výpočetní složitosti
2006/07

Vyučující: Pavel Pudlák; Jiří Sgall
Rozsah v ZS: 0/2 Z
Rozsah v LS: 0/2 Z

Anotace

Seminář zaměřený na výpočetní složitost a související kombinatorické problémy. Referují se zejména aktuální články a výsledky účastníků a hostů semináře. Je vhodný pro studenty, kteří se chtějí specializovat v této oblasti a pro doktorandy. Některé referáty budou v angličtině. Aktuální informace na adrese http://www.math.cas.cz/~sgall/complexity/.

Osnova

Výběr témat se přizpůsobuje zájmům účastníků. V poslední době jsme se zabývali těmito oblastmi:

• Sublineární algoritmy
• Kódy a jejich použití v teorii složitosti.
• Reprezentace pomocí polynomů a použití algebraických metod ve složitosti.
• Exponenciální algoritmy pro NP-úplné problémy.
• Booleovská složitost, dolní odhady výpočetní složitosti explicitních funkcí, branching programy. Dolní odhady pro výrokové kalkuly.
• Komunikační složitost. Souvislosti složitosti s algebraickými pojmy: rank, rigidita matic, vlastnosti řídkých a cirkulantních matic.
• Kombinatorické problémy související se složitostí. Expandery. Extremální kombinatorika množinových systémů.
• Vztahy mezi existencí složitých funkcí a derandomizací pravděpodobnostních algoritmů.

Literatura

Většinou aktuální články v angličtině.

Další informace

Seminář se koná v Matematickém ústavu v Žitné 25. Úmluva bude v rámci hromadné úmluvy na výběrové přednášky KAM v prvním týdnu semestru.

Kontakt:
sgall@math.cas.cz, http://www.math.cas.cz/~sgall/, tel. 222 090 780;
pudlak@math.cas.cz, http://www.math.cas.cz/~pudlak/, tel. 222 090 721.