RNDr. Ondřej Suchý, Ph.D.

2022 - 2024

Parameterized or multivariate analysis became in the last two decades a standard approach for (NP-) hard computational problems. Here, in contrast to classical complexity, the efficiency of algorithms is not measured only with respect to the length of the input instance, but also with respect to a specified parameter. The outcome is a more fine grained complexity landscape which allows for a better prediction of the complexity of particular instances encountered. The goal is to design algorithms with running time that is polynomial in the input size and exponential only in the designated parameter. Fundamentally, the degree of the polynomial is required to be independent of the value of the parameter. Parameterized complexity provides a mathematical framework to analyze these algorithms and also to show that for some problems and parameters there is (probably) no such algorithm.

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.

2014 - 2016

Parameterized algorithmics became in the last two decades a standard tool to solve computationally hard (NP-hard) problems. The running time here is expressed in terms of a secondary measure (the parameter) additionally to the input size, which provides a more refined analysis of where the hardness of the problem comes from. Parameterized complexity provides a mathematical framework to analyze these algorithms and also to show that for some problems and parameters there is (probably) no such algorithm. In this research proposal we plan to study several open questions related to fundamental problems in the field of network design within the framework of parameterized complexity. More precisely, we will focus on the following two areas: Steiner-type problems in graphs; Network Measurement, Navigation, and Resource Placement. We plan to provide a systematic multivariate complexity analysis, which we feel is missing in the area.

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.

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

A parameterized or multivariate analysis became in the last two decades a standard approach for (NP-) hard computational problems. Here, in contrast to classical complexity, the efficiency of algorithms is not measured only with respect to the length of the input instance, but also with respect to a specified parameter. Recently, more focus is put on achieving the best possible polynomial degree as well as the best asymptotic time dependency on the parameter. This is justified by providing matching lower bounds, showing that the existence of significantly faster algorithms is improbable, typically relying on the Exponential Time Hypothesis or its strong form. In this research proposal we target on several fundamental problems in network design related to connectivity in directed graphs from the parameterized perspective. Our aim is to either obtain new algorithms for the problems with better running time than that of the existing algorithms, or to obtain lower bounds showing that such an improvement is unlikely. Our main focus are Steiner-type problems in directed graphs.