2026-07-24T00:34:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13261 2024-03-06T10:51:58Z ddc:004 open_access

Lower Bounds for Semi-adaptive Data Structures via Corruption Dvořák, Pavel Loff, Bruno semi-adaptive dynamic data structure polynomial lower bound corruption bound information theory 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₁,… ,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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pavel Dvořák and Bruno Loff 2020 Is Part Of LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2020.20 urn:nbn:de:0030-drops-132617 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.20 eng https://creativecommons.org/licenses/by/3.0/legalcode