2014
2015
2016
2017
2018
2019
2020
2022
2023
2024

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 obvykle schází jednou za měsíc ve čtvrtek v 16:15 a to buď v budově FEL ČVUT nebo v budově MFF UK.

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

Pražský informatický seminář je z důvodů prevence šíření nákazy novým koronavirem do odvolání pozastaven.