Lower Bounds for Semi-adaptive Data Structures via Corruption

05/05/2020
by   Pavel Dvořák, et al.
0

In a dynamic data structure problem we wish to maintain an encoding of some data in memory, in such a way that we may efficiently carry out a sequence of queries and updates to the data. A long-standing open problem in this area is to prove an unconditional polynomial lower bound of a trade-off between the update time and the query time of an adaptive dynamic data structure computing some explicit function. Ko and Weinstein provided such lower bound for a restricted class of semi-adaptive data structures, which compute the Disjointness function. There, the data are subsets x_1,…,x_k and y of {1,…,n}, the updates can modify y (by inserting and removing elements), and the queries are an index i ∈{1,…,k} (query i should answer whether x_i and y are disjoint, i.e., it should compute the Disjointness function applied to (x_i, y)). The semi-adaptiveness places a restriction in how the data structure can be accessed in order to answer a query. We generalize the lower bound of Ko and Weinstein to work not just for the Disjointness, but for any function having high complexity under the smooth corruption bound.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset