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 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.
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ě.
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.
© 2013-2022, Prague Computer Science Seminar 
Toto dílo podléhá licenciCreative Commons Attribution 4.0 International License.
