Společný seminář DIMEA a FORMELA

Podzim 2022 - přehled rozvrhu

Matas Šileikis (Akademie věd ČR): Procesy převracení grafů

Pondělí 19. září, 14:00, místnost C417

Uvažujme grafový proces v diskrétním čase, kde v každém kroku rovnoměrně náhodně vybereme k-tice vrcholů a podgraf, který vyvolá, transformujeme podle předem definovaného pravidla, například "vidíš-li kliku, odstraň všechny její hrany" nebo "cokoliv vidíš, nahraď náhodným grafem G(k,1/2)". Ukážeme, jak převést otázku o koncentraci tohoto procesu (pro kvadratický počet kroků) na dynamický systém v prostoru grafů. Uvážíme několik příkladů jednoduchých pravidel a budeme uvažovat pravidlo, které dává vzniknout periodické trajektorii.
Přednáška vychází z práce s P. Araújem, F. Garbem, J. Hladkým, E. K. Hngem a F. Skermanem.

Navid Talebanfard (Akademie věd ČR): Varianta VC-rozměru s aplikacemi na obvody s hloubkou 3

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

Zavádíme novou analogii známé VC-dimenze. Ukazujeme, že pro tento pojem lze významně překonat odpovídající Sauer-Shelahovu hranici. Toho využijeme k pokroku v řešení extrémního problému vznikajícího v oblasti složitosti obvodů.
Jedná se o společnou práci s Peterem Franklem a Svjatoslavem Gryaznovem.

Marta Grobelna (TU Mnichov): Syntéza regulátorů pro multiagentní systémy

Pondělí 10. října, 14:00, místnost C417

Víceagentové systémy (MAS) se skládají z více výpočetních jednotek, tzv. agentů, které společně řeší úlohy. Zejména složitá úloha je rozdělena na jednodušší úlohy a rozdělena mezi agenty podle jejich schopností. Každý agent je vybaven senzory pro snímání prostředí a komunikačními moduly, které mu umožnily vyměňovat si informace s ostatními agenty, aby mohl rozhodovat o společných akcích, které splní zadaný úkol. Díky vysoké míře flexibility mají MAS mnoho oblastí použití, například v robotice, počítačových sítích nebo inteligentních sítích. Vzhledem k tomu, že většina prostředí, kde mohou být MAS nasazeny, je kritická z hlediska bezpečnosti, je zajištění bezpečnosti těchto systémů klíčové. Formální metody jsou matematicky přísné přístupy, které lze k poskytnutí takových záruk použít.
V této přednášce se zaměřím na syntézu regulátorů, jejímž cílem je automaticky syntetizovat požadovaný systém z jeho specifikace. Výhodou syntézy oproti verifikaci je, že poskytuje systém správný po konstrukci, takže následný krok verifikace je nadbytečný. Abychom pochopili jejich význam, uvedu přehled různých přístupů k syntéze, které lze na MAS použít, a nakonec nastíním naši představu o kaskádách her.

Matěj Konečný (Univerzita Karlova): Rozšíření částečných automorfismů

Pondělí 31. října, 14:00, místnost C417

Parciální automorfismus grafu je izomorfismus mezi indukovanými podgrafy grafu. V roce 1992 Hruškovski jako klíčovou součást řešení problému v teorii modelů dokázal následující čistě kombinatorický výsledek: Pro každý konečný graf G existuje konečný graf H obsahující G jako indukovaný podgraf tak, že každý parciální automorfismus G se rozšiřuje na automorfismus H. Od té doby byly analogické výsledky dokázány pro různé další třídy struktur a souvislost s teorií modelů byla dobře prokázána. V této přednášce podám přehled této oblasti.

Tomasz Krawczyk (Jagellonská univerzita): PQ-stromy pro grafy s kruhovým obloukem -- některé aplikace

Pondělí 7. listopadu, 14:00, místnost C417

V roce 2019 Krawczyk (na základě myšlenek Hsu) navrhl PQ-strom pro grafy s kruhovým obloukem, což je datová struktura, která umožňuje reprezentovat všechny kanonické modely průsečíků grafu s kruhovým obloukem. Ve své přednášce ukážu několik příkladů, jak tuto datovou strukturu využít k efektivnímu řešení některých výpočetních problémů ve třídě kruhových obloukových grafů, jako je kanonizace a izomorfismus. Probereme také některé výsledky, které nám umožňují hledat kanonický model grafu s kruhovým obloukem, který splňuje určité podmínky s ohledem na Hellyho vlastnost.
Některé výsledky zmíněné v přednášce jsou společnou prací s Denizem Ağaoğlu Çağırıcım, Janem Derbiszem a Grzegorzem Gutowskim.

Marcin Briański (Jagellonská univerzita): Zakázání indukovaného uspořádaného podgrafu -- některé výsledky o χ-ohraničenosti

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

Na zkoumání tříd grafů omezených χ lze pohlížet jako na snahu pochopit, jaké struktury, kromě klik, nutí graf mít vysoké chromatické číslo. Jak se dalo očekávat vzhledem k NP-tvrdosti barvení grafů, není snadné tuto otázku zodpovědět, což dokazuje mnoho dlouho otevřených problémů v této oblasti, přičemž Gyárfásova-Sumnerova domněnka (je třída grafů bez pevného lesa jako indukovaného podgrafu χ-omezená?) je obzvláště významným příkladem.
Poněkud odlišným způsobem konstrukce zajímavé třídy grafů je zákaz indukovaného uspořádaného podgrafu, kdy uvažujeme všechny naše grafy společně s nějakým lineárním uspořádáním na množině vrcholů a požadujeme, aby podgraf byl s tímto uspořádáním konzistentní. Jako příklad lze tímto způsobem snadno definovat třídy grafů srovnatelnosti a akordických grafů - dvě velmi důkladně prozkoumané podtřídy dokonalých grafů. Přirozenou otázkou, kterou si lze položit, je, pro které uspořádané grafy H vede zakázání H jako indukovaného uspořádaného podgrafu k vytvoření třídy grafů s χ-mezí? Vzhledem k existenci grafů s velkým obvodem a vysokým chromatickým číslem musí být každý takový H (bez ohledu na uspořádání) acyklický, avšak na rozdíl od neuspořádaného případu známe mnoho příkladů uspořádaných lesů, které nedávají třídu grafů ohraničenou χ. Ve skutečnosti dosud nebyla vyslovena žádná obecná domněnka o tom, kdy zákaz uspořádaného lesa dává třídu grafů omezenou na χ.
V této přednášce představím některé známé výsledky na toto téma, zejména nastíním důkaz, že zakázání jakéhokoli indukovaného uspořádaného párování vždy dává χ-omezenou třídu grafů.
Tato přednáška vychází ze společné práce s Jamesem Daviesem, Rose McCarthy a Bartoszem Walczakem.

Stefanie Mohr a Calvin Chau (TU Mnichov): Verifikace neuronových sítí

Pondělí 21. listopadu, 14:00, místnost C417

Přednáška bude mít dvě části. V první přednášce se Stefanie bude věnovat krátkému úvodu do neuronových sítí a přehledu technik jejich ověřování. Druhou přednášku povede Calvin, který se ponoří do přístupu k verifikaci neuronových sítí založeného na abstrakci.

První abstrakt: Vzhledem k tomu, že se Neuronové sítě v posledních letech hodně zdokonalily, začínají se objevovat v bezpečnostně kritických systémech. Aby byla zajištěna jejich bezpečnost a to, že dodržují určité specifikace, existují různé metody, které se snaží ověřit jejich chování. V této přednášce uvedu krátký úvod a přehled těchto technik.

Druhý abstrakt: V této přednášce představíme abstrakční přístup ke kompresi velikosti sítí, který usnadňuje proces verifikace. Náš přístup je založen na sémantické podobnosti neuronů a ke zmenšení velikosti sítě využívá lineární programování a ortogonální projekci. Dále popisujeme, jak lze naši abstrakci zpřesnit, což potenciálně umožňuje přístup zpřesnění abstrakce řízené protipříkladem (CEGAR).

Kush Grover a Muqsit Azeem (TU Mnichov): Stochastické hry

Pondělí 28. listopadu, 14:00, místnost C417

Seminář se bude skládat ze dvou částí. První přednáška bude stručným úvodem do stochastických her a druhá přednáška se bude zabývat jejich aplikací tím, že ukáže, jak lze modelovat a řešit reálný problém jako stochastickou hru.

První přednáška: První přednáška bude věnována verifikaci souběžných stochastických her.

Souběžné hry s dosažitelností patří do rodiny stochastických her hraných na grafech. V této přednášce stručně představím souběžné stochastické hry s cíli dosažitelnosti, porovnám je s tahovými hrami a uvedu přehled technik z literatury k jejich řešení.

Druhá přednáška: Zaručené kompromisy v dynamických hrách se sledováním informačních toků

Budu hovořit o bezpečnostních rizicích v podobě pokročilých trvalých hrozeb (APT) a jejich detekci pomocí dynamického sledování informačních toků (DIFT). Sledování a detekci modelujeme jako stochastickou hru mezi útočníkem a obráncem. Řešení těchto her nám poskytuje kompromisy mezi efektivitou zdrojů při sledování a účinností detekce.

Tereza Klimošová (Univerzita Karlova): O Vizingově otázce barvení hran

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

Ve svém zásadním článku o barvení hran z roku 1965 Vizing dokázal, že z libovolného správného barvení hran lze sérií Kempeho změn dosáhnout (Δ+1)-barvení hran, kde Δ je maximální stupeň grafu. V závěru článku klade následující otázku: Lze z libovolného správného barvení hran dosáhnout sérií Kempeho změn optimálního barvení hran? Jinými slovy, pokud je graf Δ-barvený, můžeme vždy dosáhnout Δ-barvení hran? Na tuto otázku odpovíme kladně pro grafy bez trojúhelníků.

Společná práce s Marthe Bonamy, Oscarem Defrainem, Aurélie Lagoutte a Jonathanem Narbonim.