Complexity of dynamic data structures

Abstract

Sorting is one of the fundamental problems in computer science. In this thesis we present three individual results. Asymptotically optimal sorting networks have been created by Ajtai et al. [1983]. But Asharov et al. [2021] have observed that boolean circuits based on sorting networks are not optimal for sorting short integers. We present a construction of even smaller boolean circuits for sorting short integers. Lower bounds for offline Oblivious RAM have been connected to lower bounds for sorting circuits by Boyle and Naor [2016]. Larsen and Nielsen [2018] have shown a lower bound for online Oblivious RAM. We provide a lower bound for online Oblivious RAM in a more general model. Finally we provide an algorithm with expected running time O(n log log(n)) for sort- ing integers on random access machine with word length between log(n) and log(n) cubed. This algorithm does not match the expected running time of the algorithm of Han and Thorup [2002], but our algorithm is much easier to implement and analyse. 1

Třídění je jedním z fundamentálních problémů informatiky. V této práci prezentujeme tři výsledky. Asymptoticky optimální třídící sítě byly popsány v článku Ajtai a kol. [1983]. Ale Asharov a kol. [2021] ukázali, že booleovské obvody vytvořené z třídících sítí nejsou optimální pro třídění krátkých celých čísel. My ukazujeme konstrukci ještě menších obvodů pro třídění krátkých celých čísel. Dolní odhady pro offline Oblivious RAM byly spojeny s dolními odhady pro třídící booleovské obvody v článku Boyle a Naor [2016]. Larsen a Nielsen [2018] ukázali dolní odhad pro online Oblivious RAM. My ukazujeme dolní odhad pro online Oblivious RAM v obecnějším modelu. Nakonec ukazujeme algoritmus se střední dobou běhu O(n log log(n)) pro třídění celých čísel na RAM s délkou slov mezi log(n) a log(n) na třetí. Tento algoritmus ne- dosahuje střední doby běhu algoritmu z článku Han a Thorup [2002], ale náš algoritmus je mnohem jednodušší na implementaci i analýzu. 1