|
|
Limits of Data Structures, Communication, and Cards
Dvořák, Pavel ; Koucký, Michal (advisor) ; Hansen, Kristoffer Arnsfelt (referee) ; Chakrabarti, Amit (referee)
Limits of Data Structures, Communication, and Cards - Abstract In this thesis, we study several aspects of computational complexity. One of the main topics is the complexity of data structures, which are algorithms for efficient storing data supporting efficient queries to the data. In the case of dynamic data structures, they also allow modification of the data before querying. A long-standing open problem in this area is to prove an unconditional polynomial lower bound of the trade-off between the update time and the query time of an adaptive dynamic data structure computing some explicit function. We provide an unconditional polynomial lower bound for a restricted class of semi-adaptive dynamic data structures computing functions of large corruption bound, that generalizes the result by Ko and Weinstein [FOCS '20] who provided such a lower bound for data structures computing the Disjointness function. Further, we provide conditional lower bounds for certain static data structures computing permutation inversion, and polynomial evaluation and inversion. These lower bounds beat the best-known unconditional lower bounds for the problems of interest. Further, we study the communication complexity of the elimination problem, which is a prob- lem closely related to the direct sum. In the elimination problem, Alice...
|
guest ::
