doc. RNDr. Dušan Knop, Ph.D.

Projekty

Algorithms and Game Comonads

Program
Horizon Europe
Poskytovatel
Evropská komise
Kód
101111373
Období
2024 - 2026
Popis
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.

Anonymizing of User Data: A Parameterized Perspective

Program
Projekty MŠMT nezahrnuté do CEP
Poskytovatel
Ministerstvo školství, mládeže a tělovýchovy
Období
2022
Popis
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.

FIT - Fioravantes, Foivos

Program
CTU Global Postdoc Fellowship
Období
2022 - 2024
Popis
Fixed-parameter tractability and approximation algorithms are nowadays standard tools for design of algorithms for hard problems in the area of Computational Social Choice. Surprisingly, kernelization, a prominent technique in FPT algorithmics, is not used as often to tackle social choice problems. Kernelization is a formalism of safe data reduction which we believe does have its place in all research disciplines dealing with large and complex datasets. The most recent approach is the so-called lossy kernelization which on the one hand cooperates with approximation algorithms (unlike kernelization which can only be pipelined with exact algorithms) and on the other hand, allows circumventing hardness results (in exchange for introducing a possible loss in the quality of the solution).

Mobility ČVUT MSCA-F-CZ-III

Program
Operační program Jan Amos Komenský
Poskytovatel
Evropská komise
Kód
, CZ.02.01.01/00/22_010/0008601
Období
2024 - 2026
Popis
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.

New Frontiers in Computational Social Choice

Program
Projekty podpořené z ČR (pracovní kód k dodatečnému upřesnění)
Poskytovatel
Jiný tuzemský poskytovatel
Období
2022
Popis
New Frontiers in Computational Social Choice

Nové výzvy ve výpočetní sociální volbě

Program
Standardní projekty
Poskytovatel
Grantová agentura České republiky
Kód
GA22-19557S
Období
2022 - 2024
Popis
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.

Strukturální přístup pro různorodost stabilních řešení

Program
Podpora mobility výzkumných pracovníků a pracovnic v rámci mezinárodní spolupráce ve VaVaI
Poskytovatel
Ministerstvo školství, mládeže a tělovýchovy
Kód
8J21AT021
Období
2021 - 2022
Popis
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ě.