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

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.

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.

2023 - 2024

xxxxxxxxxx

2022 - 2024

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).

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.

2026 - 2031

The vision of NCUI is to build a center for applied research in the field of artificial intelligence that combines scientific excellence with social responsibility to create a positive impact on the Czech economy and society. The center develops an open and secure AI ecosystem based on trustworthy technologies, supports interdisciplinary collaboration, consolidates national research capacities, and ensures the transfer of technologies and knowledge from academia to industry as well as to public policymaking through a science-for-policy approach.

2022 - 2024

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). This project aims on filling this gap of usage of these tools in computational social choice. The suggested line of research continues our current studies in this area and the new proposed directions will need novel algorithmic approaches as they focus on the boundaries of traceability. We have identified several interesting questions where there is potential to apply the above. Our aim is to significantly deepen our understanding of these computationally hard problems by providing polynomial-sized (lossy) kernels or showing that the problems are resistant to this line of attack.

2022

New Frontiers in Computational Social Choice

2026 - 2028

Pathfinding in graphs is one of the most fundamental problems in graph theory. Dijkstra’s algorithm for finding shortest paths between nodes has been a part of standard computer science curriculum for decades. However, in several applications in logistics and operations research, the desired path should satisfy some additional constraints, and thus cannot be found by a straight-forward application of Dijkstra’s algorithm. For example, on some crossroads turning right is not permitted, i.e. certain edges of the graph cannot appear as consecutive edges on the path. Another example occurs in rideshare route planning, where each pick-up location needs to be visited before the corresponding destination. In other words, the ordering of the vertices on the path needs to respect a given partial order. Yet another case is travel planning: it is often convenient to choose connecting flights that belong to the same airline alliance. This can be modeled as an edge-colored weighted graph, where we are searching for the shortest monochromatic path. The three above scenarios might seem very different, but they share one key property that makes pathfinding difficult. Namely, Dijkstra’s algorithm relies on triangle inequality, which does not hold in the above cases. The aim of this project is to design novel algorithms that overcome this obstacle and to conduct a systematic study on different variants of the pathfinding problem with traversal constraints. To achieve this, we will employ parameterized complexity tools, whichenable us to study the complexity of problems with respect to multiple parameters describing theinput and output data.

2025

Konference STIGMA je určena studentům a mladým vědeckým pracovníkům nejen z ČVUT, ale i z dalších univerzit a institucí. Letos se bude konat již desátý ročník této konference. STIGMA poskytuje prostor pro prezentaci vědecké práce, sdílení poznatků, diskuzi nad aktuálními problémy a navázání nových kontaktů. Zvláštní důraz je kladen na inspiraci k dalšímu výzkumu a podnícení zájmu o vědeckou práci. Každý den konference bude rozdělen do několika přednáškových bloků, přičemž zbylý čas bude věnován řešení otevřených problémů a diskuzím. Doktorandi a studenti představí přednášky zaměřené buď na vlastní výzkum, nebo na aktuální vědecké výsledky související s tématy konference. Mladí vědečtí pracovníci pak nabídnou inspirativní přednášky, jejichž cílem bude motivovat studenty k budoucímu výzkumu a navrhnout vhodné problémy k řešení. Letos nově plánujeme do programu také zařadit půldenní workshop zaměřený na hlubší představení jedné konkrétní oblasti výzkumu. Tématicky je konference vymezena na tyto oblasti: - teoretická informatika - diskrétní matematika - teorie grafů - výpočetní složitost a algoritmy - datové struktury

2026

Konference STIGMA je určena studentům a mladým vědeckým pracovníkům nejen z ČVUT, ale i z dalších univerzit a institucí. Letos se bude konat již jedenáctý ročník této konference. STIGMA poskytuje prostor pro prezentaci vědecké práce, sdílení poznatků, diskuzi nad aktuálními problémy a navázání nových kontaktů. Zvláštní důraz je kladen na inspiraci k dalšímu výzkumu a podnícení zájmu o vědeckou práci. Každý den konference bude rozdělen do několika přednáškových bloků, přičemž zbylý čas bude věnován řešení otevřených problémů a diskuzím. Doktorandi a studenti představí přednášky zaměřené buď na vlastní výzkum, nebo na aktuální vědecké výsledky související s tématy konference. Mladí vědečtí pracovníci pak nabídnou inspirativní přednášky, jejichž cílem bude motivovat studenty k budoucímu výzkumu a navrhnout 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

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ě.