|
|
Limits of Data Structures, Communication, and Cards
Dvořák, Pavel ; Koucký, Michal (vedoucí práce) ; Hansen, Kristoffer Arnsfelt (oponent) ; Chakrabarti, Amit (oponent)
Limity datových struktur, komunikace a karet - abstrakt V této práci studujeme několik aspektů výpočetní složitosti. Jedno z hlavních témat je složitost datových struktur, což jsou algoritmy pro efektivní ukládání dat podporující efektivní dotazy na daná data. Dynamické datové struktury také umožňují měnit data před dotazem. Dlouho otevřený problém v této oblasti je dokázat nepodmíněný polynomiální dolní odhad na porovnání času na editaci a času na dotaz adaptivní dynamické struktury počítající nějakou explicitní funkci. Ukazujeme nepodmíněný polynomiální dolní odhad pro omezenou třídu semi-adaptivních dy- namických datových struktur počítající funkce s velkou korupční mezí, což zobecňuje výsledek od Ko a Weinsteina [FOCS '20], kteří ukázali takový dolní odhad pro datové struktury počítající funkci disjunkce. Dále ukazujeme podmíněný dolní odhad pro určité statické datové struktury počítající inverzi permutací, a vyhodnocení a interpolaci polynomů. Tyto dolní odhady jsou lepší než nejlepší známé nepodmíněné dolní odhady pro dané problémy. Dále studujeme komunikační složitost eliminačního problému, který je velmi blízký problému přímého součtu. U eliminačního problému, Alenka a...
|
host ::
RSS.