2014
2015
2016
2017
2018

Třicátéčtvrté setkání Pražského informatického semináře

Libor Barto

Symetrie ve výpočetní složitosti

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ě.

22. března 2018

16:00

Posluchárna E-107, FEL ČVUT
Karlovo nám. 13, Praha 2
Zobrazit na mapě

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

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í zpravidla 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ě.

Seminář připravuje organizační výbor ve složení Roman Barták (MFF UK), Jaroslav Hlinka (ÚI AV ČR), Michal Chytil, Pavel Kordík (FIT ČVUT), Michal Koucký (MFF UK), 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), Tomáš Werner (FEL ČVUT), 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.

Podporovatelé

Kontakt