Společný seminář DIMEA a FORMELA

Jaro 2023 - přehled rozvrhu

Ondřej Lengál (Vysoké učení technické v Brně): Nejnovější vývoj v oblasti doplňování omega-automatů

Pondělí 27. února, 14:00, místnost C417

Automaty akceptující omega-regulární jazyky, jako jsou Büchiho automaty, jsou základním nástrojem pro modelovou kontrolu vlastností životaschopnosti, dokazování terminace programů nebo rozhodování logik, jako je S1S. Efektivní algoritmy pro jejich komplementaci jsou nezbytnou součástí sady nástrojů omega-automatů. Popíšu náš nedávný pokrok v této oblasti.

Přednáška vychází ze společné práce s Vojtou Havlenou, Bárou Šmahlíkovou (oba FIT VUT), Yong Li a Andreou Turrinim (oba Čínská akademie věd).

Alexandru Malekshahian (King's College London): O pravděpodobnosti, že G(n,p) je bipartitní

Pondělí 6. března, 14:00, místnost C417

V této přednášce se budu zabývat následující základní otázkou: Jaká je pravděpodobnost, že Erdősův-Renyiho náhodný graf G(n,p) je bipartitní? V souvislosti se svou prací o řešitelnosti náhodných booleovských rovnic studovali Pittel a Yeum tento problém v okně kolem kritické pravděpodobnosti p=1/n. V této přednášce se zaměřím na nadkritický režim p=c/n, kde c>1, a budu diskutovat přístup k tomuto problému prostřednictvím studia modelu náhodného shluku ze statistické fyziky.

Společná práce s Matthewem Jenssenem a Willem Perkinsem.

Matjaž Krnc (Primorská univerzita): Grafy se dvěma moplexy jsou více než dokonalé.

Pondělí 13. března, 14:00, místnost C417

Moplex je přirozená grafová struktura, která vzniká při vyzdvižení klasické Diracovy věty z chordálních grafů na obecné grafy. V případě chordických grafů platí, že mít nejvýše dva simpliciální moduly nutí graf být intervalový. V této přednášce se zaměříme na grafy obsahující 2 moplexy, které tvoří protějšek třídy intervalových grafů. Ukážeme, že všechny grafy s 2 moplexy jsou dokonalé. Přesněji řečeno, třída všech spojitých 2-moplexových grafů je vklíněna mezi vlastní intervalové grafy a grafy s kokomparabilitou (obě inkluze jsou těsné pro dědičné třídy). Ukážeme také, že každý spojitý 2-moplexový graf obsahuje hamiltonovskou cestu (na rozdíl od grafů kokomparability). Na druhou stranu ukazujeme, že izomorfismus grafů a Max-Cut zůstávají NP-těžké (na rozdíl od intervalových grafů).

Vycházíme ze společné práce s Clémentem Dallardem, Robertem Ganianem, Meike Hatzelovou a Martinem Milaničem.

Jae-baek Lee (University of Victoria): Odpojené společné grafy prostřednictvím přesycení

Pondělí 20. března, 14:00, místnost C417

O grafu H se říká, že je společný, pokud je počet označených monochromatických kopií H ve dvoubarevném vybarvení hran velkého úplného grafu asymptoticky minimalizován náhodným vybarvením. Je známo, že disjunktní sjednocení dvou společných grafů nemusí být společné; např. grafy K_2 a K_3 jsou společné, ale jejich disjunktní sjednocení společné není. Najdeme první dvojici neobvyklých grafů, jejichž disjunktní unie je společná, a společný graf a neobvyklý graf, jejichž disjunktní unie je společná. Náš přístup spočívá v redukci problému, který má ukázat, že určité nespojité grafy jsou společné, na omezený optimalizační problém, v němž jsou omezení odvozena ze supersaturačních mezí souvisejících s Razborovou větou o hustotě trojúhelníků.

Alberto Espuny Díaz (TU Ilmenau): Práh pro (některé) rozpínací stromy v náhodných geometrických grafech

Pondělí 27. března, 14:00, místnost C417

Uvažujme následující model náhodných grafů: celkem n vrcholů je nezávisle na sobě přiřazeno do rovnoměrně náhodných pozic na jednotkovém čtverci a libovolné dva vrcholy jsou pak spojeny hranou, pokud je vzdálenost mezi jejich pozicemi menší než daný parametr r. Tento model se nazývá náhodný geometrický graf G(n,r) a podobně jako u binomického náhodného grafu G(n,p) vykazují rostoucí vlastnosti prahové hodnoty (vzhledem k parametru r), kterým chceme porozumět. Chování náhodných geometrických grafů se však velmi liší od chování G(n,p). V této přednášce zdůrazním některé z těchto rozdílů a nakonec se zaměřím na případ vyvážených s-árních stromů, pro které jsme stanovili práh. Vycházím přitom ze společné práce s Ljubenem Lichevem, Dieterem Mitsche a Alexandrou Wesolek.

Jakub Gajarský (Varšavská univerzita): Šířka dvojčat, řídkost, stabilita a zmrazení

Pondělí 3. dubna, 14:00, místnost C417

Twin-width je grafově-teoretický pojem, který zavedli Bonnet a kol. v roce 2020. Za krátkou dobu od svého zavedení vzbudil velkou pozornost, a to především proto, že je jednak poměrně obecný (zobecňuje např. grafy s omezenou šířkou kliky, grafy s vyloučeným menším a množiny s omezenou šířkou), jednak má stále dobré strukturní, kombinatorické a algoritmické vlastnosti.

Teorie řídkých grafů, kterou rozvinuli Nešetřil a Ossona de Mendez, je velmi úspěšným přístupem ke zobecnění mnoha běžně studovaných pojmů teorie grafů (například planárních grafů, grafů s omezeným stupněm, grafů s vyloučeným minorem) a ke studiu řídkých grafů z jednotného pohledu a v posledních 15 letech vedla k mnoha zajímavým výsledkům.

Monadická stabilita je pojem z teorie modelů, který má původ v práci Saharona Shelaha v jeho klasifikačním programu pro logické teorie. V současné době se monadicky stabilní třídy grafů dostávají do stále většího zájmu badatelů v oblasti teorie grafů a algoritmiky, a to díky nově nalezeným a domnělým souvislostem mezi logikou a strukturní teorií grafů.

V přednášce popíšu dva výsledky, které vysvětlují, jak spolu souvisejí pojmy šířka dvojčat, řídkost a monadická stabilita. Poté představím techniku zvanou "zmrazení", která je použitelná pro grafy s omezenou šířkou dvojčat a která byla použita při důkazech výše uvedených výsledků.

Magdalena Prorok (AGH University): Směrové grafy bez duhových trojúhelníků

Pondělí 17. dubna, 14:00, místnost C417

Jednou z nejzákladnějších otázek teorie grafů je Mantelova věta, která určuje maximální počet hran v grafu bez trojúhelníků řádu n. Nedávno byla vyřešena barevná varianta tohoto problému. V této variantě uvažujeme k grafů na společné množině vrcholů, přičemž každý graf považujeme za hrany v odlišné barvě, a chceme určit nejmenší počet hran v každé barvě, který zaručuje existenci duhového trojúhelníku.

V této přednášce řešíme analogický problém pro směrové grafy bez duhových trojúhelníků, ať už směrové nebo tranzitivní, pro libovolný počet barev. Konstrukce a důkazy se zásadně liší pro k=3 a k≥4 a typ zakázaného trojúhelníku.

Jedná se o společnou práci se Sebastianem Babińskim a Andrzejem Grzesikem.

Keat Hng (Akademie věd ČR): Aproximace frakčně izomorfních grafů

Pondělí 24. dubna, 14:00, místnost C417

Frakční izomorfismus konečných grafů je důležitý a dobře prozkoumaný koncept na pomezí teorie grafů a kombinatorické optimalizace. Má mnoho různých charakterizací, které zahrnují řadu velmi odlišných a zdánlivě nesouvisejících vlastností grafů. Nedávno Grebík a Rocha rozvinuli teorii frakčního izomorfismu pro grafony, tj. limity hustých posloupností grafů, kde ukázali, že každá charakterizace frakčního izomorfismu v grafech má dobře definovaný grafonový protějšek a že to jsou skutečně všechny ekvivalentní charakterizace frakčního izomorfismu pro grafony. Položili si otázku, zda lze zlomkově izomorfní grafony charakterizovat jako limity posloupností grafů, které jsou vstupně zlomkově izomorfní (ve smyslu grafů). Na jejich otázku odpovídáme kladně.

Jedná se o společnou práci s Janem Hladkým.

Alessandro Abate (Oxfordská univerzita): Logika se setkává s učením - formální syntéza s neuronovými šablonami

Čtvrtek 18. května, 14:00, místnost C417

Představím nedávnou práci na CEGIS, rámci "induktivní syntézy řízené protipříkladem" pro úlohy zvukové syntézy, které jsou relevantní pro dynamické modely, problémy řízení a softwarové programy. Rámec induktivní syntézy zahrnuje interakci dvou komponent, učícího se a ověřujícího. Učící se subjekt trénuje neuronovou šablonu na konečných vzorcích. Ověřovač spolehlivě ověřuje kandidáty vycvičené učícím se subjektem pomocí volání řešitele SAT-modulo-teorie. Kdykoli kandidát není platný, SMT generované protipříklady jsou předány učícímu se subjektu k dalšímu tréninku. Objasním vnitřnosti rámce CEGIS a ukážu jeho fungování na několika problémech: syntéza Ljapunovových funkcí a bariérových certifikátů; hybridizace nelineární dynamiky pro ověřování bezpečnosti; syntéza digitálních regulátorů pro spojitá zařízení; a aplikace v autonomii v reálném čase.

Alessandro Abate je profesorem verifikace a řízení na katedře informatiky Oxfordské univerzity, kde je také zástupcem vedoucího katedry. Dříve se věnoval výzkumu na Stanfordově univerzitě a ve společnosti SRI International a působil jako odborný asistent v Delft Center for Systems and Control na TU Delft. Získal titul MS/PhD na univerzitě v Padově a na Kalifornské univerzitě v Berkeley. Jeho výzkumné zájmy spočívají ve formální verifikaci a řízení stochastických hybridních systémů a v jejich aplikacích v kyberfyzikálních systémech, zejména v oblasti kritické bezpečnosti a energetiky. Mísí v sobě techniky strojového učení a umělé inteligence, jako je bayesovská inference, posilování učení a teorie her.

Djordje Žikelić (IST Rakousko): Dordžike Žikelić: formální verifikace a řízení nekonečně stavových stochastických systémů založené na učení.

Pondělí 5. června, 14:00, místnost C417

Stochastické systémy poskytují formální model pro systémy, které vykazují neurčité chování. Na rozdíl od jejich konečných protějšků jsou však formální verifikace a řízení nekonečně stavových stochastických systémů méně známé. Tato přednáška bude obhajovat použití metod založených na martingalech pro formální verifikaci a syntézu regulátorů v nekonečně stavových stochastických systémech. Hlavní výhodou metod založených na martingalech je, že poskytují formální záruky a zároveň umožňují plně automatizovanou verifikaci a algoritmy řízení s aplikacemi v programovacích jazycích, teorii řízení a umělé inteligenci. V této přednášce představíme nové metody založené na martingalech pro statickou analýzu pravděpodobnostních programů a pro syntézu regulátorů ve stochastických dynamických systémech. Konkrétně u posledně jmenovaných představíme první rámec pro učení a formální ověřování neuronových regulátorů ve stochastických systémech.

James Main (Univerzita v Monsu): Různé tahy v náhodných strategiích

Pondělí 12. června, 14:00, místnost C417

Hry dvou hráčů na (případně stochastických) grafech jsou v teoretické informatice rozšířeným modelem. Pozoruhodné je, že takové hry jsou užitečné v kontextu reaktivní syntézy, tj. pro automatický návrh systémů, které se chovají dobře bez ohledu na chování prostředí, s nímž interagují. Optimální strategie ve hrách na grafech mohou vyžadovat randomizaci, pokud se jedná o inherentně pravděpodobnostní cíle, vyvažování více cílů nebo v kontextech částečných informací. Neexistuje žádný jedinečný způsob, jak definovat náhodné strategie. Lze například použít tzv. smíšené strategie nebo behaviorální strategie. V nejobecnějších nastaveních nemají tyto dvě třídy stejnou vyjadřovací schopnost. Zásadní výsledek v teorii her - Kuhnova věta - tvrdí jejich ekvivalenci ve hrách s dokonalou pamětí. tento výsledek se zásadně opírá o možnost strategií využívat nekonečnou paměť, tj. neomezenou znalost všech minulých pozorování. Počítačové systémy jsou však v praxi konečné. Proto je vhodné omezit naši pozornost na strategie s konečnou pamětí, definované jako automaty s výstupy. V nich lze náhodnost implementovat různými způsoby: inicializace, výstupy nebo přechody mohou být náhodné, respektive deterministické. V závislosti na tom, které aspekty jsou randomizovány, se liší vyjadřovací schopnosti příslušné třídy strategií s konečnou pamětí.

V této přednášce poskytneme úplnou taxonomii tříd strategií s konečnou pamětí, které získáme změnou toho, která ze tří výše uvedených složek je randomizována.