Akce ČVUT

34. PIS - Libor Barto: Symetrie ve výpočetní složitosti

22.03.2018   16:00-18:00

ANOTACE PŘEDNÁŠKY:

V posledních 20 letech bylo dosaženo velkého pokroku ve zkoumání výpočetní složitosti problémů splnitelnosti omezujících podmínek, a to zejména díky využití souvislosti mezi jejich výpočetní složitostí a jistým pojmem zachycujícím symetrie problémů v této třídě.

V přednášce budu mluvit o této souvislosti a o mé vizi, že se nakonec stane jedním ze základních principů teorie výpočetní složitosti a povede k vyřešení zásadních problémů oboru, jako je domněnka nazývaná Unique Games Conjecture nebo dokonce problém P versus NP.

PŘEDNÁŠEJÍCÍ:

Libor Barto je docentem na Katedře algebry MFF UK. Zabývá se univerzální algebrou a výpočetní složitostí, zejména problémy splnitelnosti omezujících podmínek. Mezi jeho známé práce patří objev teorie absorpce, která vedla např. k charakterizaci problémů řešitelných lokálními metodami. Je řešitelem ERC Consolidator grantu Symetrie ve výpočetní složitosti. Titul Ph.D. získal v roce 2006 na MFF UK, v letech 2010 až 2012 pracoval na McMaster University v Kanadě.

O PRAŽSKÉM INFORMATICKÉM SEMINÁŘI:

Seminář se schází vždy 4. čtvrtek v měsíci v 16 hod. (s výjimkou letních měsíců a prosince), a to buď v budově FEL ČVUT na Karlově náměstí, nebo v budově MFF UK na Malostranském náměstí.
Jeho program je tvořen hodinovou přednáškou, po níž následuje časově neomezená diskuse. Základem přednášky je něco (v mezinárodním měřítku) mimořádného nebo aspoň pozoruhodného, na co přednášející přišel a co vysvětlí způsobem srozumitelným a zajímavým i pro širší informatickou obec. Přednášky jsou standardně v angličtině.
Formát semináře připravil přípravný výbor ve složení Michal Chytil (ÚI AVČR), Pavel Kordík (FIT ČVUT), Jan Kybic (FEL ČVUT), Michal Pěchouček (FEL ČVUT), Jiří Sgall (MFF UK), Vojtěch Svátek (FIS VŠE), Michal Šorel (ÚTIA AV ČR), Filip Železný (FEL ČVUT)

Idea Pražského informatického semináře vznikla z rozhovorů představitelů několika vědeckých institucí na téma, jak odstranit zbytečnou fragmentaci informatické komunity v ČR.

Místo konání

KN:E-107 (Zengerova posluchárna), FEL, budova E, Karlovo nám. 13, Praha 2

Pořadatel

Přípravný výbor PIS

Kontaktní osoba

Aneta Klaudis, klaudane@fel.cvut.cz, 224 35 7667

Podrobnější informace

http://praguecomputerscience.cz/index.php?l=cz&p=34