Combinatorial Methods in Information Theory
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
—
CEP - equivalent branches <br>(according to the <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">converter</a>)
AF - Documentation, librarianship, work with information<br>BC - Theory and management systems<br>BD - Information theory<br>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