License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2020.20
URN: urn:nbn:de:0030-drops-132617
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13261/
Dvořák, Pavel ;
Loff, Bruno
Lower Bounds for Semi-adaptive Data Structures via Corruption
Abstract
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.
BibTeX - Entry
@InProceedings{dvok_et_al:LIPIcs:2020:13261,
author = {Pavel Dvoř{\'a}k and Bruno Loff},
title = {{Lower Bounds for Semi-adaptive Data Structures via Corruption}},
booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
pages = {20:1--20:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-174-0},
ISSN = {1868-8969},
year = {2020},
volume = {182},
editor = {Nitin Saxena and Sunil Simon},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13261},
URN = {urn:nbn:de:0030-drops-132617},
doi = {10.4230/LIPIcs.FSTTCS.2020.20},
annote = {Keywords: semi-adaptive dynamic data structure, polynomial lower bound, corruption bound, information theory}
}
|
Keywords: |
|
semi-adaptive dynamic data structure, polynomial lower bound, corruption bound, information theory |
|
Collection: |
|
40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
04.12.2020 |
