Seminář o základech výpočetní techniky

Tento výzkumný seminář poskytuje prostor pro prezentaci výsledků výzkumu týkajícího se návrhu algoritmů, diskrétní matematiky, formálních metod, logiky a příbuzných oblastí teoretické informatiky. Seminář společně pořádají výzkumné laboratoře DIMEA, FORMELA a LIVE. Seminář navazuje na seminář FMDSA , který v minulosti pořádala laboratoř FORMELA.

Čas a místo konání

Seminář se koná v pondělí ve 14 hodin semestrálního času v místnosti C417 v budově Fakulty informatiky v (zhruba) týdenním rozvrhu.

Jaro 2024 - přehled rozvrhu

Nadcházející přednášející

Liana Khazaliya (TU Vídeň): Vzestupná a ortogonální rovinnost jsou W[1]-tvrdé parametrizované šířkou stromu

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

Testování vzestupné planarity a ortogonální planarity jsou ústředními problémy v kreslení grafů. Je známo, že oba jsou NP-úplné, ale XP, když jsou parametrizovány šířkou stromu [Orthogonal: GD'19; Upward: SoCG'22]. V této přednášce ukážu, že tyto dva problémy jsou W[1]-tvrdé parametrizované šířkou stromu, což je odpověď na otevřené problémy položené ve dvou dřívějších článcích. Klíčovým krokem v našem důkazu je analýza problému All-or-Nothing Flow, jehož zobecnění bylo použito jako mezikrok v důkazu NP-úplnosti pro oba problémy testování planarity. Dokážeme, že problém toku je W[1]-hard parametrizovaný šířkou stromu na planárních grafech a že existující řetězec redukcí na problémy testování planarity lze upravit, aniž by se šířka stromu zvětšila. Naše redukce také ukazují, že známé algoritmy s časem n^{O(tw)} nelze vylepšit tak, aby běžely v čase n^{o(tw)}, pokud neselže hypotéza exponenciálního času.

Společná práce s Bartem M. P. Jansenem, Philippem Kindermannem, Giuseppem Liottou, Fabriziem Montecchianim a Kirillem Simonovem.

Martin Dzúrik (Masarykova univerzita): Kombinační spektra grafů

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

Kombinatorická spektra grafů jsou zobecněním H-Hamiltonových spekter. Hlavní motivací bylo vytvořit z H-Hamiltonových spekter operaci a rozvinout některé algebry v této oblasti. Vylepšená verze této operace tvoří komutativní monoid. Nejdůležitější je, že většinu základních pojmů teorie grafů, jako je maximální párování, konektivita a barvení vrcholů a hran, Ramseyho čísla, izomorfismy a regulárnost, lze vyjádřit v jazyce této operace.

Preprint z Arxivu je k dispozici zde

Marek Filakovský (Masarykova univerzita): Topologické metody pro slibované homomorfismy - tvrdost lineárně uspořádaného 4-obarvení 3-barevných 3-uniformních hypergrafů

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

Lineárně uspořádané (LO) k-obarvení hypergrafu je obarvení jeho vrcholů barvami [1,...,k] tak, že každá hrana obsahuje jedinečnou maximální barvu. Rozhodování o tom, zda vstupní hypergraf připouští LO k-obarvení s pevným počtem barev, je NP-úplné (a ve speciálním případě grafů se LO obarvení shoduje s obvyklým obarvením grafu). Zde zkoumáme složitost aproximace "lineárně uspořádaného chromatického čísla" hypergrafu. Dokážeme, že následující slibný problém je NP-úplný: Rozlište případ, kdy je hypergraf LO 3-barevný, a případ, kdy není ani LO 4-barevný. Tento výsledek dokazujeme kombinací algebraických, topologických a kombinatorických metod, přičemž vycházíme z topologického přístupu ke studiu přibližného barvení grafů, který zavedli Krokhin, Opršal, Wrochna a Živný (2023), a rozšiřujeme jej.

společná práce s Nakajimou, Opršalem, Tasinatem a Wagnerem.

Samuel Braunfeld (Univerzita Karlova): Některé interakce mezi teorií modelů a strukturní teorií grafů

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

Budeme diskutovat o tom, jak lze modelově-teoretické koncepty zabývající se oddělením krotkého a divokého chování ve třídách nekonečných struktur a rozvojem teorie struktur pro krotké třídy aplikovat na třídy konečných struktur, přičemž dojde k interakci s programy ve strukturální teorii grafů. Tyto koncepty stály zejména za významným pokrokem v poslední době při určování, kdy je obecný algoritmický problém kontroly modelů prvního řádu (s pevnými parametry) řešitelný.

Igor Balla (Masarykova univerzita): Malé kódy a barvení množin Ramseyho čísel

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

Určení maximálního počtu jednotkových vektorů v R^r bez párového vnitřního součinu většího než alfa je základním problémem geometrie a teorie kódování. V roce 1955 Rankin tento problém vyřešil pro všechna alfa ≤ 0 a v této přednášce ukážeme, že maximum je (2 + o(1))r pro všechna 0 ≤ alfa ≪ r^(-2/3), čímž odpovíme na otázku Bukha a Coxe. Navíc exponent -2/3 je nejlepší možný. V důsledku toho získáme horní mez na velikost q-árního kódu s délkou bloku r a vzdáleností (1 - 1/q)r - o(r^(1/3)), která je těsná až na multiplikativní faktor 2(1 - 1/q) + o(1) pro libovolnou prvočíselnou mocninu q a nekonečně mnoho r. Když q = 2, řeší to v silné formě Tietäväinenovu domněnku z roku 1980 a exponent 1/3 je nejlepší možný. Nakonec s využitím nedávno objevené souvislosti s q-árními kódy získáme analogický výsledek pro barvení množin Ramseyho čísel.

Kaushik Mallik (ISTA): Plánování založené na aukci: Modulární rámec pro víceúčelové rozhodování.

Pondělí 6. května, 14:00, místnost C417

Úlohy sekvenčního rozhodování často vyžadují splnění více částečně protichůdných cílů. Stávající přístupy jsou monolitické, kdy jediná politika splňuje všechny cíle. Představím rozvrhování založené na aukci, nový modulární rámec pro víceúčelové sekvenční rozhodování. V tomto rámci je každý cíl splněn pomocí samostatné a nezávislé politiky. Politiky jsou pak složeny pomocí nového mechanismu skládání za běhu, kdy v každém kroku musí dražit z předem přidělených rozpočtů o privilegium výběru další akce. Licitace podněcuje politiky, aby upravily své nabídky podle naléhavosti svých akcí, a ten, kdo nabídne nejvyšší cenu, dostane plán jako první. Studujeme následující problém decentralizované syntézy: Jak sestavit politiky vybavené licitací, jejichž složení splní současně všechny cíle? Představím řešení problému decentralizované syntézy pro plánování cest na konečných grafech se dvěma časovými cíli.

Jan Böker (Cáchy): Složitost rekonstruovatelnosti homomorfismů

Pondělí 27. května, 14:00, místnost C417

Reprezentace grafů pomocí počtů jejich homomorfismů vedla v posledních letech ke krásné teorii nerozlišitelnosti homomorfismů. Počty homomorfismů mají navíc slibné aplikace v teorii databází a strojovém učení, kde bychom chtěli odpovídat na dotazy nebo klasifikovat grafy pouze na základě reprezentace grafu G jako konečného vektoru počtů homomorfismů z nějaké pevné konečné množiny grafů do G. Studujeme výpočetní složitost pravděpodobně nejzákladnějšího výpočetního problému spojeného s těmito reprezentacemi, problému rekonstruovatelnosti homomorfismů: je dána konečná posloupnost grafů a odpovídající vektor přirozených čísel, rozhodněte, zda existuje graf G, který realizuje daný vektor jako počty homomorfismů z daných grafů.

Ukážeme, že tento problém dává přirozený příklad NP^{#P}-těžkého problému, který může být ještě NP-těžký, když se omezí na pevný počet vstupních grafů omezené šířky stromu a pevný vstupní vektor přirozených čísel, případně když se omezí na konečnou vstupní množinu grafů. Dále ukážeme, že při omezení na konečnou vstupní množinu grafů a při zadání horní meze řádu grafu G jako dalšího vstupu nemůže být problém NP-těžký, pokud P = NP. Pro tento režim získáme částečně pozitivní výsledky. Zkoumáme také parametrizovanou složitost problému a poskytujeme fpt-algoritmy pro případ, že je zadán jediný graf a že je zadáno více grafů stejného řádu s počty podgrafů místo homomorfismů.

Jedná se o společnou práci s Louisem Härtelem, Ninou Runde, Timem Seppeltem a Christophem Standkem.

Alexandru Malekshahian (Londýn): O typické struktuře antiřetězců v booleovské mřížce.

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

Stará Dedekindova otázka se ptá na počet antiřetězců (monotónních booleovských funkcí) v booleovské mřížce na $n$ prvcích. Po dlouhé řadě stále přesnějších výsledků určil Koršunov tento počet až na multiplikativní faktor (1+o(1)). Vracíme se k Dedekindovu problému a studujeme typickou strukturu antiřetězců pomocí nástrojů z pravděpodobnosti a statistické fyziky. To vede k řadě výsledků, které zahrnují zpřesnění Koršunovovy asymptotiky, asymptotiku pro počet antiřetězců pevné velikosti a "řídkou" verzi Spernerovy věty.

Společná práce s Matthewem Jenssenem a Jinyoung Parkem.

Felix Schröder (Univerzita Karlova): Hustotní vzorec pro mimorovinné grafy

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

Zavedeme vzorec hustoty pro (topologické) kresby grafů v rovině nebo na kouli, který dává do vztahu počet hran, vrcholů, křížení a velikostí buněk v kresbě. Jeho schopnost demonstrujeme na několika aplikacích: dokazujeme těsné horní meze hustoty hran různých tříd mimorovinných grafů, včetně takzvaných $k$-rovinných grafů s $k=1,2$, vějířovitě se křížících / vějířovitě rovinných grafů, $k$-ohýbaných RAC-grafů s $k=0,1,2$ a kvaziplanárních grafů. V některých případech (1$-ohybové a 2$-ohybové RAC-grafy a vějířovitě křížové / vějířovitě rovinné grafy) tak získáme první těsné horní meze hustoty hran příslušných tříd grafů. V jiných případech podáváme nové zjednodušené a podstatně kratší důkazy pro meze, které již byly v literatuře známy. Díky vzorci hustoty jsou všechny naše důkazy většinou elementárně počítané a většinou obcházejí typickou složitou případovou analýzu, která se vyskytovala v dřívějších důkazech. Dále v některých případech (jednoduché a nehomotopické kvaziplanární grafy) vedou naše alternativní důkazy využívající vzorec hustoty k prvním příkladům těsných dolních hranic.

Společná práce s Matthewem Jenssenem a Jinyoung Parkem.

Teodor Knapik (Université de la Nouvelle Calédonie): Lindenmayerovy jazyky grafů, teorie prvního řádu a expandéry.

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

Expandéry, které si Kolmogorov představil v polovině minulého století, tvoří pozoruhodné rodiny grafů s aplikacemi v tak rozmanitých oblastech, jako jsou robustní komunikační sítě a pravděpodobnostně kontrolovatelné důkazy, abychom jmenovali alespoň dvě. Od důkazu existence expandérů uplynulo několik let, než se podařilo přijít s explicitní algebraickou konstrukcí [Margulis 1973] některých rodin expandérů. Jejich první elementární (kombinatorická) konstrukce byla publikována v roce 2002 a v roce 2009 oceněna Gödelovou cenou.

V této přednášce představíme rámec, který zachycuje většinu známých kombinatorických konstrukcí expandérů. Je založen na zobecnění Lindenmayerových systémů na oblast grafů. Tento formalismus nazýváme Lindenmayerovy grafové gramatiky. Indentifikujeme několik základních vlastností, které umožňují rozhodnout problém kontroly jazyka vzhledem k větám prvního řádu. Tento výsledek získáme zahrnutím jazyka grafů do automatické struktury. Kontrolou jazyka v tomto konkrétním kontextu rozumíme následující problém.

Příklad: Lindenmayerova grafová gramatika a věta prvního řádu Otázka: Existuje v tomto jazyce graf, pro který tato věta platí?

Shibashis Guha (TIFR, Indie): Syntéza strategie pro globální okno PCTL

Pondělí 15. července, 14:00, místnost C417

Je dán markovský rozhodovací proces (MDP) M a formule Phi, problém syntézy strategie se ptá, zda existuje strategie sigma taková, že výsledný markovský řetězec M[sigma] splňuje Phi. Je známo, že tento problém je pro pravděpodobnostní temporální logiku PCTL nerozhodnutelný. Studujeme třídu formulí, které lze považovat za fragment PCTL, kde je po celou dobu provádění vynucována lokální vlastnost omezeného horizontu. Navíc v pravděpodobnostních nerovnostech připouštíme lineární výrazy. Tato logika je na hranici rozhodnutelnosti v závislosti na typu uvažovaných strategií. Konkrétně se ukazuje, že syntéza strategií je rozhodnutelná, pokud jsou strategie deterministické, zatímco pro libovolné strategie je problém nerozhodnutelný.

Společná práce s Benjaminem Bordaisem, Damienem Busatto-Gastonem a Jeanem-Françoisem Raskinem.

Gaston Burrull (BiCMR, Peking, Čína): O domněnce o kombinatorické invarianci.

Středa 17. července, 14:00, místnost C417

Domněnka vyslovená G. Lusztigem (nepublikovaná počátkem 80. let) a nezávisle na něm M. Dyerem (1987) předpovídá, že pokud jsou dva Bruhatovy intervaly [x, y] a [x', y'] (případně různých Coxeterových systémů) izomorfní jako částečně uspořádané množiny, pak se odpovídající Kazhdanovy-Lusztigovy polynomy rovnají, tj. platí Px,y(q) = Px',y'(q). To je fascinující domněnka, kterou se v posledních desetiletích zabývaly desítky matematiků. V této přednášce vysvětlím něco z historie, dílčí výsledky a mé malé porozumění tomuto tématu.