Kombinatorické metody v teorii informace

Poskytovatel

Grantová agentura České republiky

Program

POSTDOC INDIVIDUAL FELLOWSHIP

Veřejná soutěž

SGA0202200002

Hlavní účastníci

Univerzita Karlova / Matematicko-fyzikální fakulta

Druh soutěže

VS - Veřejná soutěž

Číslo smlouvy

22-14872O

Název projektu anglicky

Combinatorial Methods in Information Theory

Anotace anglicky

The aim of this project is to study current problems in complexity, in particular lower bounds of data structures, and related notions like lifting theorems and network coding. The main aim is to narrow the gap between the current lower bounds and upper bounds of dynamic data structure or to indicate why the improvement is hard by relating it with other hard problems in complexity. Further, I plan to study what is the right complexity measure of functions for which we can prove a lifting theorem, which relates the communication complexity and decision tree complexity of functions. Recently, it was proved that the network coding conjecture (NCC) implies various computational lower bounds (including bounds for data structures). NCC asserts that for undirected graphs the network coding does not bring any advantage over multicommodity flows. I plan to study a connection of NCC with other computational problems and if the conjecture holds for various graph classes, which would yield unconditional computational lower bounds.

Kategorie VaV

ZV - Základní výzkum

OECD FORD - hlavní obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

OECD FORD - vedlejší obor

—

OECD FORD - další vedlejší obor

—

CEP - odpovídající obory <br>(dle <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">převodníku</a>)

AF - Dokumentace, knihovnictví, práce s informacemi<br>BC - Teorie a systémy řízení<br>BD - Teorie informace<br>IN - Informatika

Zahájení řešení

1. 1. 2022

Ukončení řešení

31. 12. 2025

Poslední stav řešení

B - Běžící víceletý projekt

Poslední uvolnění podpory

14. 9. 2022

Důvěrnost údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Systémové označení dodávky dat

CEP23-GA0-GN-R

Datum dodání záznamu

20. 2. 2023

Celkové uznané náklady

4 129 tis. Kč

Výše podpory ze státního rozpočtu

4 069 tis. Kč

Ostatní veřejné zdroje financování

0 tis. Kč

Neveřejné tuz. a zahr. zdroje finan.

0 tis. Kč