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

Zajišťuje: KAM
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:

• 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ů.

Základní literatura

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

Doplň.popis

Seminář se koná v Matematickém ústavu v Žitné 25.

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.

15. 4. 2005