Sylabus
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.
- Booleovská složitost, dolní odhady výpočetní složitosti explicitních funkcí, formule, branching programy.
- Dolní odhady pro výrokové kalkuly.
- Komunikační složitost.
- Kombinatorické problémy související se složitostí. Expandery. Extremální kombinatorika množinových systémů.
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/.