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

Zajišťuje: KAM
Vyučující: Pavel Pudlák; Jiří Sgall
Rozsah v ZS: 0/2 Z
Rozsah v LS: 0/2 Z
Třída: I

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:

• 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, pro LS 2004 předpokládáme zachování termínu ve středu po obědě.
Na hromadné úmluvě na výběrové přednášky KAM lze případně domluvit mírnou změnu termínu.

Kontakt:
sgall@math.cas.cz, http://www.math.cas.cz/~sgall/, tel. 22090780;
pudlak@math.cas.cz, http://www.math.cas.cz/~pudlak/, tel. 22090721.

1. 2. 2005