Mgr. Lenka Fryčová

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

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 - 2025

Realizace vrcholů grafu v rovině nebo jiném prostoru se nazývá tuhá, pokud existuje pouze konečně mnoho jiných realizací daného grafu se stejnými délkami hran (až na shodná zobrazení). Pokud naopak můžeme realizaci spojitě deformovat při zachování délek hran, nazýváme ji pohyblivou. Jelikož tuhost je generická vlastnost, má smysl nazvat samotný graf tuhý, pokud je jeho libovolná generická realizace tuhá. Nicméně, i tuhý graf může mít pohyblivé, negenerické, realizace. Tyto paradoxní situace jsou předmětem tohoto projektu. S využitím algebraické geometrie bylo nedávno ukázáno, že graf má paradoxní pohyblivou realizaci v rovině, pokud pro něj existuje jisté hranové obarvení. Cílem tohoto projektu je zkombinovat teorii grafů a kombinatoriku se sofistikovanějšími nástroji algebraické geometrie ke zkoumání paradoxní pohyblivosti v širším smyslu. Zajímají nás symetricky pohyblivé realizace, různá zobecnění konceptu tuhosti nebo realizace na algebraických plochách, třídy grafů relevantní pro aplikace do senzorových sítí či již zmíněná hranová obarvení.

2023 - 2027

The RiGiD project lays the groundwork for this research programme and aims to develop a methodology for rigorous engineering of data analysis pipelines that can be adopted in practice. Our approach is pragmatic. Rather than chasing functional correctness, we hope to substantially reduce the incidence of errors in the wild. The research is structured in three overlapping chapters. First, identify the problem by carrying out user studies and large-scale program analysis of a corpus of over 100,000 data science pipelines. The outcome will be a catalog of error patterns as well as a labeled dataset to be shared with other researchers. The technical advances will focus on combining dynamic and static program analysis to approximate the behavior of partial programs and programs written in highly dynamic languages. The second part of our effort proposes a methodology and tooling for developing data sciences codes with reduced error rates. The technical contributions of this part of the project focus on lightweight specification techniques and, in particular, the development of a novel gradual typing system that deals with common programming idioms found in our corpus. This includes various forms of object orientation, data frames, and rich value specifications. These specifications are complemented with an automated test generation technique that combines test and input synthesis with fuzzing and test minimization. Finally, the execution environment is extended to support automatic reproducibility and result audits through data lineage. The third and last part of the work evaluates the proposal by conducting user studies and developing tools for automating deployment. The contribution will be a qualitative and quantitative assessment of the RiGiD methodology and tooling. The technical contribution will be tools that leverage program analysis to infer approximate specifications to assist deployment and adoption. Our tools target R, a language for data analytics with 2 milli

2023 - 2027

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