Projekty

2022 - 2024

Projekt (ve specifickém cíli B) si klade za cíl vytvoření nového magisterského studijního programu Kvantová informatika s výrazným podílem informatiky. Má připravovat odborníky pro technologickou a technickou praxi spojenou s druhou kvantovou revolucí umožňující radikálně nové výpočetní a řídící postupy a komunikaci s bezprecedentní bezpečností. Absolventi budou vybaveni řadou inženýrských dovedností a budou schopni zavádět kvantové postupy na pracovištích orientovaných na pokročilé technologie. Přepokládá se zapojení čtyř fakult ČVUT, a to FEL, FIT, FS a FJFI. Jednotlivé fakulty mají komplementární kompetence potřebné k zavedení a rozvíjení studijního programu Kvantová informatika, a to na magisterském stupni. Důraz bude kladen na informatické a inženýrské aspekty kvantové informatiky. Pro jednotlivé fakulty jsou zajímavé odpovídající směry (komunikace, počítání a metrologie) s různou vahou. Předpokládá se realizace dvou laboratoří kvantové komunikace a kryptografie (FEL, FJFI) a kvantového počítání (FIT, FS, FJFI, FEL). Vybudované laboratoře budou k dispozici všem fakultám v rámci výuky. Na FITu vznikne laboratoř kvantového počítání. Z projektu vybavíme učebnu(y) simulátorem optického kvantového počítače. Fakulta bude rozvíjet kvantovou informatiku, zejména se bude zaměřovat na kvantové algoritmy pro paralelizaci výpočtů, kryptování/šifrování, bezpečnostní algoritmy, teorii složitosti, data mining (učení paralelních struktur – sítě s hlubokým učením). FEL a FJFI společně vytvoří výukovou laboratoř kvantové kryptografie a její následné napojení na národní kryptografickou síť. Projekt by měl sloužit i k přípravě studijních programů/specializací na součástech ČVUT (FJFI, FIT, FEL, FS). Dále bude snahou se aktivně zapojit do vznikajícího mezinárodního konsorcia pro kvantové technologie.

2022 - 2024

Pro návrh algoritmů na řešení těžkých problémů v oblasti výpočetní sociální volby jsou dnes standardem jak parametrizované tak aproximační algoritmy. Kernelizace, jedna z hlavních technik v parametrizované složitosti, je překvapivě málo používána pro řešení problémů sociální volby. Jsme přesvědčeni, že kernelizace -- formalismus pro bezpečnou redukci vstupních dat -- má své místo ve všech výzkumných odvětvích týkajících se velkých vstupních dat. Nejnovějšı́ koncept je tzv. ztrátová kernelizace, která je jednak použitelná v kombinaci s aproximačními algoritmy (narozdíl od normální kernelizace, kterou lze kombinovat pouze s exaktními algoritmy), a druhak dokáže obejít těžkostní výsledky za cenu zavedení mírné nepřesnosti do výsledku. Navrhujeme aplikovat tyto moderní nástroje -- ztrátovou kernelizaci -- ve výpočetní sociální volbě. Navrhovaný projekt navazuje na naši předchozí práci v tomto oboru a uvažované směřování výzkumu bude vyžadovat nové algoritmické přı́stupy. Vytipovali jsme řadu zajímavých otevřených problémů a otázek, kde vidíme potenciál dosáhnout výsledků aplikováním zmíněných technik. Cílem je významně prohloubit poznání výpočetní složitosti těchto problémů nalezením polynomiálně velkých (ztrátových) kernelů popřípadě vyloučit jejich existenci.

2021 - 2022

Výpočetní kolektivní volba (Computational Social Choice) je moderní oblast informatiky, ve které se setkává teoretická informatika a teorie her (ekonomie). Mnoho zásadních problémů v této oblasti je NP-těžkých, proto se začala v poslední dekádě stále častěji uplatňovat tzv. parametrizovaná analýza, která si klade za cíl identifikovat parametry, jejichž zafixování na malých hodnotách vede k efektivní řešitelnosti daného problému. V předkládaném projektu se hodláme zaměřit na strukturální parametry (mezi nejznámější bezpochyby patří stromová šířka) vstupních instancí, čímž omezíme například vzájemnou interakci mezi agenty hledajícími kolektivní rozhodnutí a podobně.

2017 - 2019

Parametrizovaná nebo multivarietní analýza se v minulých dvou dekádách stala standardním přístupem k (NP-) těžkým problémům. Oproti klasické výpočetní složitosti se zde efektivita algoritmů měří nejen vzhledem k délce vstupu, ale také vzhledem k určenému parametru. V poslední době je kladen větší důraz na získání nejlepšího možného stupně polynomu stejně jako nejlepší asymptotické závislosti na parametru. To je prokázáno předvedením dolních mezí ukazujících, že existence výrazně rychlejších algoritmů je nepravděpodobná, typicky založených na hypotéze exponenciálního času, nebo její silné formě. V tomto návrhu projektu se zaměřujeme na několik zásadních problémů v návrhu sítí spojených se souvislostí v orientovaných grafech z parametrizovaného pohledu. Náš cíl je získat nové algoritmy pro tyto problémy s lepší časovou složitostí než mají existující algoritmy, nebo získat dolní meze ukazující, že takové vylepšení je nepravděpodobné. Naším hlavním zaměřením jsou problémy Steinerovského typu na orientovaných grafech.

2014 - 2016

Parametrizované algoritmy se staly v posledních dvou dekádách standardním nástrojem pro řešení výpočetně těžkých (NP-těžkých) problémů. Časová složitost se v tomto vyjadřuje pomocí druhotné míry (parametru) navíc k velikosti vstupu, čímž se dosahuje jemnější analýza původu těžkosti problému. Parametrizovaná složitost představuje matematický rámec pro analyzování takových algoritmů a také umožnuje ukázat, že pro některé problémy a parametry (pravděpodobně) žádný takový algoritmus neexistuje. V rámci toho projektu plánujeme studovat některé otevřené otázky související se základními problémy v oblasti návrhu sítí z pohledu parametrizované složitosti. Přesněji se zaměříme na tyto dvě oblasti: problémy Steinerovského typu v grafech a měření, navigace a umístění zdrojů v sítích. Plánujeme připravit systematickou multivarietní analýzu, která podle našeho názoru v této oblasti chybí.

2018

Jedná se již o 4. ročník této konference. Cílem konference STIGMA je poskytnout studentům a mladým vědeckým pracovníkům prostor pro prezentaci jejich vědecké práce a činnosti mezi sebou, příležitost naučit se novým technikám a postupům z aktuálních vědeckých výsledků, nabídnout čas, ve kterém mohou účastníci řešit otevřené problémy, a v neposlední řadě též příležitost navázat mezi sebou kontakty. Během dne proběhne několik přednáškových bloků. Zbývající čas je vyhrazen na řešení problémů a diskuze. Doktorandi a studenti přednesou přednášky týkající se buďto jejich vlastního výzkumu, nebo aktuálního vědeckého výsledku zapadajícího do tématiky konference. Mladí vědečtí pracovníci přednesou přednášky, které budou mít za cíl inspirovat studenty k budoucímu výzkumu a nabídnou tak vhodné problémy k řešení. Tématicky je konference vymezena na tyto oblasti: - teoretická informatika - diskrétní matematika - teorie grafů - výpočetní složitost a algoritmy - datové struktury Konference je určena především pro doktorandy a studenty ČVUT, kteří na ní budou mít přednášku.

2017

Jedná se již o 3. ročník této konference. Cílem konference STIGMA je poskytnout studentům a mladým vědeckým pracovníkům prostor pro prezentaci jejich vědecké práce a činnosti mezi sebou, příležitost naučit se novým technikám a postupům z aktuálních vědeckých výsledků, nabídnout čas, ve kterém mohou účastníci řešit otevřené problémy, a v neposlední řadě též příležitost navázat mezi sebou kontakty. Během dne proběhne několik přednáškových bloků. Zbývající čas je vyhrazen na řešení problémů a diskuze. Doktorandi a studenti přednesou přednášky týkající se buďto jejich vlastního výzkumu, nebo aktuálního vědeckého výsledku zapadajícího do tématiky konference. Mladí vědečtí pracovníci přednesou přednášky, které budou mít za cíl inspirovat studenty k budoucímu výzkumu a nabídnou tak vhodné problémy k řešení. Tématicky je konference vymezena na tyto oblasti: - teoretická informatika - diskrétní matematika - teorie grafů - výpočetní složitost a algoritmy - datové struktury Konference je určena především pro doktorandy a studenty ČVUT, kteří na ní budou mít přednášku.

2016

Cílem konference STIGMA je poskytnout studentům a mladým vědeckým pracovníkům prostor pro prezentaci jejich vědecké práce a činnosti mezi sebou, příležitost naučit se novým technikám a postupům z aktuálních vědeckých výsledků, nabídnout čas, ve kterém mohou účastníci řešit otevřené problémy, a v neposlední řadě též příležitost navázat mezi sebou kontakty. Během dne proběhne několik přednáškových bloků. Zbývající čas je vyhrazen na řešení problémů a diskuze. Doktorandi a studenti přednesou přednášky týkající se buďto jejich vlastního výzkumu, nebo aktuálního vědeckého výsledku zapadajícího do tématiky konference. Mladí vědečtí pracovníci přednesou přednášky, které budou mít za cíl inspirovat studenty k budoucímu výzkumu a nabídnou tak vhodné problémy k řešení. Tématicky je konference vymezena na tyto oblasti: - teoretická informatika - diskrétní matematika - teorie grafů - výpočetní složitost a algoritmy - datové struktury Konference je určena především pro doktorandy a studenty ČVUT, kteří na ní budou mít přednášku.

2015

Cílem konference STIGMA je poskytnout studentům a mladým vědeckým pracovníkům prostor pro prezentaci jejich vědecké práce a činnosti mezi s sebou, příležitost naučit se novým technikám a postupům z aktuálních vědeckých výsledků, nabídnout čas, ve kterém mohou účastníci řešit otevřené problémy, a v neposlední řadě též příležitost navázat mezi sebou kontakty. Během dne proběhne několik přednáškových bloků. Zbývající čas je vyhrazen na řešení problémů a diskuze. Doktorandi a studenti přednesou přednášky týkající se buďto jejich vlastního výzkumu, nebo aktuálního vědeckého výsledku zapadajícího do tematiky konference. Mladí vědečtí pracovníci přednesou přednášky, které budou mít za cíl inspirovat studenty k budoucímu výzkumu a nabídnou tak vhodné problémy. Tematicky je konference vymezena na tato témata: - teoretická informatika - diskrétní matematika - teorie grafů a grafové algoritmy - výpočetní složitost a algoritmy Konference je určena především pro doktorandy a studenty ČVUT, kteří na ní budou mít přednášku.

2023

Cílem konference STIGMA je poskytnout studentům a mladým vědeckým pracovníkům prostor pro prezentaci jejich vědecké práce a činnosti mezi sebou, příležitost naučit se novým technikám a postupům z aktuálních vědeckých výsledků, nabídnout čas, ve kterém mohou účastníci řešit otevřené problémy, a v neposlední řadě též příležitost navázat mezi sebou kontakty. Během dne proběhne několik přednáškových bloků. Zbývající čas je vyhrazen na řešení problémů a diskuze. Doktorandi a studenti přednesou přednášky týkající se buďto jejich vlastního výzkumu, nebo aktuálního vědeckého výsledku zapadajícího do tématiky konference. Mladí vědečtí pracovníci přednesou přednášky, které budou mít za cíl inspirovat studenty k budoucímu výzkumu a nabídnou tak vhodné problémy k řešení. Tématicky je konference vymezena na tyto oblasti: - teoretická informatika - diskrétní matematika - teorie grafů - výpočetní složitost a algoritmy - datové struktury Konference je určena především pro doktorandy a studenty ČVUT, kteří na ní budou mít přednášku.

2024

Cílem konference STIGMA je poskytnout studentům a mladým vědeckým pracovníkům prostor pro prezentaci jejich vědecké práce a činnosti mezi sebou, příležitost naučit se novým technikám a postupům z aktuálních vědeckých výsledků, nabídnout čas, ve kterém mohou účastníci řešit otevřené problémy, a v neposlední řadě též příležitost navázat mezi sebou kontakty. Během dne proběhne několik přednáškových bloků. Zbývající čas je vyhrazen na řešení problémů a diskuze. Doktorandi a studenti přednesou přednášky týkající se buďto jejich vlastního výzkumu, nebo aktuálního vědeckého výsledku zapadajícího do tématiky konference. Mladí vědečtí pracovníci přednesou přednášky, které budou mít za cíl inspirovat studenty k budoucímu výzkumu a nabídnou tak vhodné problémy k řešení. Tématicky je konference vymezena na tyto oblasti: - teoretická informatika - diskrétní matematika - teorie grafů - výpočetní složitost a algoritmy - datové struktury Konference je určena především pro doktorandy a studenty ČVUT, kteří na ní budou mít přednášku.

2024 - 2026

The emerging theory of game comonads establishes a fruitful interplay between category theory, mathematical logic, and algorithms. This theory has shown its power when obtaining new Lovasz-type theorems, preservation theorems and decomposition theorems in finite model theory. In our recent work we show that the theory of game comonads can be leveraged to obtain the two traditional Courcelle theorems, stating FPT decidability of monadic second order logic on classes of bounded tree-width and clique-width. This result is only a first step in concrete algorithmic applications of the theory. The abstract setting of game comonads is a good candidate for a systematic treatment of algorithmic problems. The first objective of the project is to formulate a general theory of FPT decidability in terms of game comonads. To start with, we describe some of the important model-theoretic algorithms.

2024 - 2026

V souladu s výzvou projekt umožní mezinárodní mobilitu výzkumným pracovníkům, kterým byl v minulých letech schválen projekt Horizont 2020 z programu Marie Skłodowska-Curie Individual / Postdoctoral Fellowships, jež dosáhl hodnocení alespoň 70 %, ale z důvodů nedostatku financí byl zařazen do kategorie tzv. no-money projektů. Projekt bude realizován pracovními pobyty zahraničních VP na ČVUT. Hlavním cílem projektu je podpora profesního růstu výzkumných pracovníků, kvalitního výzkumu, vzdělávání pro praxi a rozvoje komunikace a spolupráce. Na FIT se jedná o příjezdovou mobilitu na 24 měsíců výzkumného pracovníka, Foivos Fioravantes Ph.D., z Francie. Školitel je doc. Ing. Dušan Knop, Ph.D.

2024 - 2026

Navzdory zvyšujícímu se počtu úspěšných aplikací teorie her v praxi je expresivita nasazených modelů stále limitována výpočetními možnostmi existujících algoritmů pro hledání (přibližných) řešení. Jedním z omezujících faktorů je velká výpočetní složitost hledání ekvilibrií pro hry s velkými či dokonce nekonečnými prostory akcí. Navíc prostory strategií mají v aplikacích často složitou vnitřní strukturu, což složitost výpočtu ekvilibrií dále prohlubuje. Cílem projektu je proto posunout stav poznání hledáním nových podmínek pro existenci ekvilibrií ve hrách se složitými prostory strategií, návrhem nových iterativních algoritmů pro aproximaci ekvilibrií v těchto hrách, výzkumem složitosti výpočtu ekvilibrií pro speciální třídy her a aplikovat získané poznatky na různé karetní hry.

2023 - 2027

The project will be focused on several fundamental problems in discrete and computational geometry, and their surrounding (sub)areas.

2022

When collecting user data nowadays we care about these being sufficiently anonymous, that is, we usually replace the real data with some perturbed data so that we protect the sole identity of the end-user. This is a challenging task both from computational and algorithmical (theoretic) approach. Therefore we often have to employ advanced methods of analysis and algorithmic techniques to identify tractable cases. We will identify new paramaters that attain low values in realworld data and analyze if these result in fixed-parameter tractable case or to parameterized hardness.

2022

New Frontiers in Computational Social Choice