All
All

What are you looking for?

All
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

Combinatorial Methods in Information Theory

Project goals

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.

Keywords

ComplexityLower BoundsData StructuresLifting TheoremsNetwork Coding

Public support

  • Provider

    Czech Science Foundation

  • Programme

  • Call for proposals

    SGA0202200002

  • Main participants

    Univerzita Karlova / Matematicko-fyzikální fakulta

  • Contest type

    VS - Public tender

  • Contract ID

    22-14872O

Alternative language

  • Project name in Czech

    Kombinatorické metody v teorii informace

  • Annotation in Czech

    Cíl tohoto projektu je zkoumání aktuálních problémů ve složitosti, hlavně dolních odhadů datových struktur a příbuzných témat, jako jsou "pozvedávácí věty" a síťové kódování. Hlavní cíl je zmenšit rozdíl mezi současnými dolními a horními odhady dynamických datových struktur nebo naznačit, proč je toto zlepšení obtížné, pomocí nalezení souvislostí s dalšími těžkými problémy ve složitosti. Dále pak plánuji studovat, co je správná složitostní míra funkcí, pro kterou je možné dokázat "pozvedávací větu", která dává do souvislosti komunikační složitost a velikost rozhodovacích stromů funkce. V nedávné době bylo dokázáno, že domněnka síťového kódování (DSK) implikuje různé výpočetní dolní odhady (včetně odhadů pro datové struktury). DSK říká, že pro neorientované grafy síťové kódování nepřináší žádnou výhodu oproti vícekomoditním tokům. Plánují studovat vztah DSK s dalšími výpočetními problémy a zda domněnka platí pro různé třídy grafů, což by mohlo vést k nepodmíněným výpočetním dolním odhadům.

Scientific branches

  • R&D category

    ZV - Basic research

  • OECD FORD - main branch

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

  • OECD FORD - secondary branch

  • OECD FORD - another secondary branch

  • AF - Documentation, librarianship, work with information
    BC - Theory and management systems
    BD - Information theory
    IN - Informatics

Solution timeline

  • Realization period - beginning

    May 1, 2022

  • Realization period - end

    Dec 31, 2025

  • Project status

    K - Ending multi-year project

  • Latest support payment

    Feb 29, 2024

Data delivery to CEP

  • Confidentiality

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

  • Data delivery code

    CEP25-GA0-GN-R

  • Data delivery date

    Feb 21, 2025

Finance

  • Total approved costs

    4,129 thou. CZK

  • Public financial support

    4,069 thou. CZK

  • Other public sources

    0 thou. CZK

  • Non public and foreign sources

    0 thou. CZK

Basic information

Recognised costs

4 129 CZK thou.

Public support

4 069 CZK thou.

98%


Provider

Czech Science Foundation

OECD FORD

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

Solution period

01. 05. 2022 - 31. 12. 2025